原题传送门：P2604 [ZJOI2010]基站选址

看一眼题目，变知道这题一定是dp

设f[i][j]表示在第i个村庄修建第j个基站且不考虑i+1~n个村庄的最小费用

可以得出f[i][j] = Min(f[k][j - 1] + cost[k][i] ) + c[i] (j - 1 <= k < i)

其中cost[k][i]表示i~k之间没有基站所需要的费用

计算复杂度O(N)，加上循环，总复杂度O(N^2 K)

看一下数据范围K <= N，K <= 100 , N <= 20000

真棒，TLE

考虑如何优化

首先，我们发现之前的转移方程可以去掉一维j，实际上只要在最外层枚举j就可以了

f[i] = Min( f[k] + cost[k][i] ) + c[i] (j - 1 <= k < i)

主要的时间浪费在计算cost上

我们要找方法来优化

对于任意一个村庄i，记它所能被覆盖的左右边界st[i],ed[i]（最左端、最右端可以覆盖到i的基站位置，可用二分查找处理）

然后在用邻接表记录ed值为i的村庄有哪些，在这些村庄之前建立基站就覆盖不到i了。

这样当我们推导i + 1时，若从村庄1~st[k] - 1(ed[k] = i)转移过来则必定要赔偿村庄k的费用，我们就可以考虑用线段树来维护f[k] + cost[k][i]的值

即在区间[1, st[k] - 1]加上村庄k的费用，而转移即在区间[1, i - 1]找f[k] + cost[k][i]的最小值，总复杂度为O(N log N K)。

#pragma GCC optimize("O3")

#include <bits/stdc++.h>

#define N 20005

#define inf 0x3f3f3f3f

using namespace std;

inline int read()

{

    register int x=0,f=1;register char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

inline int Min(register int a,register int b)

{

    return a<b?a:b;

}

int D[N],C[N],S[N],W[N],lr[N],rr[N],f[N];

vector<int> vq[N];

int ql,qr;

struct Segment_tree{

    int minn[N<<2],tag[N<<2];

    inline void pushup(register int x)

    {

        minn[x]=Min(minn[x<<1],minn[x<<1|1]);

    }

    inline void build(register int x,register int l,register int r)

    {

        tag[x]=0;

        if(l==r)

        {

            minn[x]=f[l];

            return;

        }

        int mid=(l+r)>>1;

        build(x<<1,l,mid);

        build(x<<1|1,mid+1,r);

        pushup(x);

    }

    inline void maintain(register int x,register int l,register int r)

    {

        if(l!=r)

            pushup(x);

        minn[x]+=tag[x];

    }

    inline void update(register int x,register int l,register int r,register int v)

    {

        if(ql<=l&&qr>=r)

            tag[x]+=v;

        else

        {

            int mid=(l+r)>>1;

            if(ql<=mid)

                update(x<<1,l,mid,v);

            if(qr>mid)

                update(x<<1|1,mid+1,r,v);

        }

        maintain(x,l,r);

    }

    inline int query(register int x,register int l,register int r,register int v)

    {

        if(ql<=l&&qr>=r)

            return minn[x]+v;

        int ret=inf,mid=(l+r)>>1;

        if(ql<=mid)

            ret=Min(ret,query(x<<1,l,mid,v+tag[x]));

        if(qr>mid)

            ret=Min(ret,query(x<<1|1,mid+1,r,v+tag[x]));

        return ret;

    }

}T;

int main()

{

   	int n=read(),k=read();

   	for(register int i=2;i<=n;++i)

        D[i]=read();

    for(register int i=1;i<=n;++i)

        C[i]=read();

    for(register int i=1;i<=n;++i)

        S[i]=read();

    for(register int i=1;i<=n;++i)

        W[i]=read();

    ++n,++k;

    D[n]=inf;

    for(register int i=1;i<=n;++i)

    {

        lr[i]=lower_bound(D+1,D+n+1,D[i]-S[i])-D;

        rr[i]=lower_bound(D+1,D+n+1,D[i]+S[i])-D;

        if(D[i]+S[i]<D[rr[i]])

            --rr[i];

        vq[rr[i]].push_back(i);

    }

    int ans=inf;

    for(register int j=1;j<=k;++j)

    {

        if(j==1)

        {

            int tot=0;

            for(register int i=1;i<=n;++i)

            {

                f[i]=tot+C[i];

                for(register int tmp=0;tmp<vq[i].size();++tmp)

                    tot+=W[vq[i][tmp]];

            }

            ans=Min(ans,f[n]);

            continue;

        }

        T.build(1,1,n);

        for(register int i=1;i<=n;++i)

        {

            ql=1,qr=i-1;

            int add=qr?T.query(1,1,n,0):0;

            f[i]=add+C[i];

            for(register int tmp=0;tmp<vq[i].size();++tmp)

            {

                ql=1,qr=lr[vq[i][tmp]]-1;

                if(qr>0)

                    T.update(1,1,n,W[vq[i][tmp]]);

            }

        }

        ans=Min(ans,f[n]);

    }

    printf("%d",ans);

    return 0;

}