[ZJOI2010] 基站选址

 我感觉我缺了一个dp优化的思路
我不知道我是不是能够对状态继续优化
dp写少了。。。
确诊了

题目描述

有 NN 个村庄坐落在一条直线上，第 i(i>1)i(i>1) 个村庄距离第 11 个村庄的距离为 DiDi​。需要在这些村庄中建立不超过 KK 个通讯基站，在第 ii 个村庄建立基站的费用为 CiCi​。如果在距离第 ii 个村庄不超过 SiSi​ 的范围内建立了一个通讯基站，那么就村庄被基站覆盖了。如果第 ii 个村庄没有被覆盖，则需要向他们补偿，费用为 WiWi​。现在的问题是，选择基站的位置，使得总费用最小。

输入格式

输入文件的第一行包含两个整数 N,KN,K，含义如上所述。

第二行包含 N−1N−1 个整数，分别表示 D2,D3,⋯ ,DND2​,D3​,⋯,DN​ ，这 N−1N−1 个数是递增的。

第三行包含 NN 个整数，表示 C1,C2,⋯ ,CNC1​,C2​,⋯,CN​。

第四行包含 NN 个整数，表示 S1,S2,⋯ ,SNS1​,S2​,⋯,SN​。

第五行包含 NN 个整数，表示 W1,W2,⋯ ,WNW1​,W2​,⋯,WN​。

输出格式

输出文件中仅包含一个整数，表示最小的总费用。

输入输出样例

3 2
1 2
2 3 2
1 1 0
10 20 30

4

说明/提示

40%的数据中，N≤500N≤500；

100%的数据中，K≤NK≤N，K≤100K≤100，N≤20,000N≤20,000，Di≤1000000000Di​≤1000000000，Ci≤10000Ci​≤10000，Si≤1000000000Si​≤1000000000，Wi≤10000Wi​≤10000。

 人生中第一次写黑题，也是第一次把一道黑题完全理解，也许挺值得庆祝？

裸dp还是很好想的，f[i][j]表示第j个基站建在了i除，其他的建在了1~(i-1)上，此时满足1到i的村子的最小花费
f[i][j]=min(f[k][j-1]+cost(i,k))
j这一维度之和j-1有关，那就是和背包类似的去掉一维，因为对同一个基站不会重复转移，所有不需要倒序
很明显，我们的优化思路就是把每一次求min的操作通过数据结构变为带log的复杂度
那对于一个点i,j，我们要怎么快速计算f[k][j-1]+cost(i,k)的min呢？
如果只是f的内容是非常简单的，但是加上cost就不行了
我们想想cost的内容是什么
我们的i的循环是从后向前的，在前面已经说过了
假设我们的数据结构已经维护好了f[i][j]要用的，那我们现在考虑怎么弄出f[i+1][j]要用的
有什么变化？
i原本是有一个基站的，现在不知道了
假设i+1村庄的影响范围是(L,R)，那如果(L,i+1)这个范围没有其他基站了，也就是上一个基站建在了(1,L-1)这个范围，那答案就要加上这个村庄的补偿，再取min，对于之后的所有其他的大于i的状态，这个都是成立的
因为后面的如果要到，肯定当前这个村庄也是要被补偿或者覆盖的嘛，前面的这个位置既然再这个情况下覆盖不到，又没有其他被覆盖的可能，不就是只有补偿了，这是一个可以预计的付出
如果在(L,i-1)这个区间内有，那就不需要，直接取这个区间f数组+pay的min就好了，因为pay=0，所以就是f数组
所以我们的数据结构就需要维护f+pay的min，要支持区间加法
（pay=cost，是一个东西）
所以我们就是直接对每一个j都循环一遍n，然后一边用线段树维护对于当前i的f+pay的最小值来直接转移，最终达到O(nk*log(n))的复杂度

问题就是pay(i,j)怎么维护？而且我们其实讨论的不是i+1处建立基站，而是i+1的影响范围的右边界处
更麻烦了
用建图的方法就好了，可以在总体O（n）的时间内把每一个需要增加的点都遍历到

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read() {
    char c=getchar();ll a=0,b=1;
    for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1;
    for(;c>='0'&&c<='9';c=getchar())a=a*10+c-48;return a*b;
}
ll n,d[200001],c[200001],s[200001],w[200001],f[200001],head[200001],ed[200001],st[200001],k,tot;
ll tag[800001],v[800001];
inline ll ls(ll x){
    return (x*2);
}
inline ll rs(ll x){
    return (x*2)+1;
}
struct edge
{
    ll next,to;
}e[800001];
inline void add(ll i,ll j)
{
    e[++tot].next=head[i];
    e[tot].to=j;
    head[i]=tot;
}
void push_down(ll p)
{
    tag[ls(p)]+=tag[p];
    tag[rs(p)]+=tag[p];
    v[ls(p)]+=tag[p];
    v[rs(p)]+=tag[p];
    tag[p]=0;
}
void push_up(ll p)
{
    v[p]=min(v[ls(p)],v[rs(p)]);
}
void build(ll p,ll l,ll r) 
{
    tag[p]=0;
    if(l==r)
    {
        v[p]=f[l];
        return ;
    }
    ll mid=l+((r-l)>>1);
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    push_up(p);
}
void update(ll p,ll l,ll r,ll tl,ll tr,ll x)
{
    if(tl>tr)return ;
    if(tl<=l&&r<=tr)
    {
        v[p]+=x;
        tag[p]+=x;
        return ;
    }
    push_down(p);
    ll mid=l+((r-l)>>1);
    if(tl<=mid)update(ls(p),l,mid,tl,tr,x);
    if(tr>mid)update(rs(p),mid+1,r,tl,tr,x);
    push_up(p);
}
ll que(ll p,ll l,ll r,ll tl,ll tr)
{
    if(tl>tr)return 2147483647;
    if(tl<=l&&r<=tr)
        return v[p];
    ll mid=l+((r-l)>>1);
    push_down(p);
    ll Get=2147483647;
    if(tl<=mid)Get=min(Get,que(ls(p),l,mid,tl,tr));
    if(mid<tr)Get=min(Get,que(rs(p),mid+1,r,tl,tr));
    return Get;
}
int main()
{
//    freopen("1.in","r",stdin);
//    freopen("2.out","w",stdout);    
    n=read();k=read();
    for(ll i=2;i<=n;i++)
        d[i]=read();
    for(ll i=1;i<=n;i++)
        c[i]=read();
    for(ll i=1;i<=n;i++)
        s[i]=read();
    for(ll i=1;i<=n;i++)
        w[i]=read();
    n++,k++;d[n]=w[n]=2147483647;//×îºóÒ»¸öµãÒ²²»Ò»¶¨½¨»ùÕ¾£¬»ùÕ¾Ò²²»Ò»¶¨½¨Âú£¬¿ÉÒÔͨ¹ýÕâÖÖ°ì·¨À´¼ÆËã×îÖÕ´ð°¸
    //ËäÈ»ÆäËûµÄ°ì·¨Ò²Ò»Ñù£¬µ«ÕâÖÖ˼·»¹ÊÇºÜºÃµÄ 
    ll now=0;
    for(ll i=1;i<=n;i++)
    {
        st[i]=lower_bound(d+1,d+1+n,d[i]-s[i])-d;
        ed[i]=lower_bound(d+1,d+1+n,d[i]+s[i])-d;
        if(d[ed[i]]>d[i]+s[i])ed[i]--;
        add(ed[i],i);
    }
    for(ll i=1;i<=n;i++)//Ö»ÓÐÒ»¸ö»ùÕ¾ 
    {
        f[i]=now+c[i];
        for(ll u=head[i];u;u=e[u].next)
        {
            ll x=e[u].to;
            now+=w[x];
        }
    }
    ll ans=f[n];
    for(ll ned=2;ned<=k;ned++)
    {
        build(1,1,n);
        for(ll i=1;i<=n;i++)
        {
            f[i]=que(1,1,n,1,i-1)+c[i];
            for(ll j=head[i];j!=0;j=e[j].next)
            {
                ll u=e[j].to;
                update(1,1,n,1,st[u]-1,w[u]);
            }
        }
        ans=min(ans,f[n]);
    }
    cout<<ans<<endl;
    return 0;
}
/*
5 4
2 6 11 16 
10 6 1 7 5 
3 8 6 2 4 
4 4 6 2 7 


*/

这题的代码难度其实不高
但是思考的深度。。
这就是黑题吗
总体的思路是从朴素dp出发的，尝试对朴素dp进行优化
（哪里不行优哪里）
难绷

总体的思路。。。
在我写完之后我分析起来好难啊。。
在我这个上帝视角看来就像是遇到困难就把困难解决
但是我怎么知道我要去解决这个困难而不是换一条路呢？
像是一个拼接的题面，只是单纯的把很多东西套在一起吗
希望我下次遇到这种题面能够做出来