输入文件的率先行包蕴多少个整数N,在第i个村子建立基站的花销为Ci

Description

难点叙述

有N个村庄坐落在一条直线上,第i(i>1)个山村距离首个山村的偏离为Di。须要在那一个村庄中建立不当先K个通信基站,在第i个村落建立基站的开支为Ci。如若在距离第i个山村不超越Si的界定内建立了三个报纸公布基站,那么就村庄被基站覆盖了。如果第i个村落并未被遮住,则须求向她们填补,费用为Wi。以后的题材是,选取基站的地点,使得总开支最小。

有N个村庄坐落在一条直线上,第i(i>1)个山村距离第四个山村的偏离为Di。须求在这个村庄中建立不当先K个通信基站,在第i个村子建立基站的开支为Ci。假如在距离第i个山村不当先Si的范围内建立了2个报导基站,那么就成它被掩盖了。假使第i个村落并未被覆盖,则要求向她们填补,成本为Wi。将来的题材是,选拔基站的地点,使得总开销最小。
输入数据 (base.in) 输入文件的首先行包蕴七个整数N,K,含义如上所述。
第2行包罗N-三个整数,分别表示D2,D3,…,DN ,那N-一个数是雨后春笋的。
第1行包罗N个整数,表示C1,C2,…CN。 第4行包含N个整数,表示S1,S2,…,SN。
第四行包涵N个整数,表示W1,W2,…,WN。
Input

输入输出格式

输入格式:

 

输入文件的首先行包蕴多个整数N,K,含义如上所述。

第②行包括N-1个整数,分别代表D2,D3,…,DN ,那N-1个数是多如牛毛的。

其三行包涵N个整数,表示C1,C2,…CN。

第伍行包罗N个整数,表示S1,S2,…,SN。

第伍行包含N个整数,表示W1,W2,…,WN。

 

输出格式:

 

输出文件中仅包含三个平头,表示小小的的总成本。

 

出口文件中仅包括多个整数,表示很小的总开支。
Output

输入输出样例

输入样例#1:

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

出口样例#1:

4

3 2 1 2 2 3 2 1 1 0 10 20 30
Sample Input
4
Sample Output
百分之四十的多少中,N<=500;
百分之百的数目中,K<=N,K<=100,N<=20,000,Di<=1000000000,Ci<=一千0,Si<=一千000000,Wi<=一千0

说明

百分之四十的数据中,N<=500;

百分百的数码中,K<=N,K<=100,N<=20,000,Di<=一千000000,Ci<=一千0,Si<=1000000000,Wi<=一千0。

 

  • 记f[i][j]f[i][j]表示在第ii个村子修建第jj个基站且不考虑第i + 1i+1~nn个村庄所需的小小花费。

  • 则转移方程为f[i][j] = Min(f[k][j – 1] +
    cst[k][i]) + c[i](j – 1 \le k < i)f[i][j]=Min(f[k][j−1]+cst[k][i])+c[i](j−1≤k<i)。其中cst[k][i]cst[k][i]表示第ii~kk个村庄之间没有被基站i, ki,k覆盖的农庄所需的赔付成本,总计费用的复杂度为O(n)O(n),则总复杂度为O(n^2k)O(n​2​​k)。

  • 如此那般让人惊讶是不可以通过的,大家考虑怎么优化:

  • 首先大家发现前边的变换方程可以去掉一维jj,实际上倘若在最外层枚举jj就足以了,约等于f[i] = Min(f[k] + cst[k][i]) +
    c[i](j – 1 \le k < i)f[i]=Min(f[k]+cst[k][i])+c[i](j−1≤k<i)。

  • 而重视的损耗在测算cst[k][i]cst[k][i]上,也等于有稍许个村子要求赔偿。

  • 对此自由1个村落ii,记它所能被遮盖的左右境界st[i], ed[i]st[i],ed[i](最左端、最右端可以覆盖到ii的基站地点,可用二分查找处理),然后在用邻接表记录eded值为ii的聚落有哪些,在那几个村庄以前建立基站就覆盖不到ii了。

  • 这么当我们推导i + 1i+1时,若从村庄11~st[k] – 1(ed[k] =
    i)st[k]−1(ed[k]=i)转移过来则必然要赔偿村庄kk的费用,大家就足以考虑用线段树来维护f[k] + cst[k][i]f[k]+cst[k][i]的值,即在间隔[1, st[k] – 1][1,st[k]−1]累加村庄kk的资费,而更换即在间隔[1, i – 1][1,i−1]找f[k] + cst[k][i]f[k]+cst[k][i]的微小值,总复杂度为O(nlogn \times k)O(nlogn×k)。

可是不驾驭怎么怎么调都窘迫,。。。

 

图片 1图片 2

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<cstring>
  6 #include<algorithm>
  7 #include<queue>
  8 #define INF 0x7ffff
  9 #define ls k<<1
 10 #define rs k<<1|1
 11 using namespace std;
 12 const int MAXN=4e4+5;
 13 inline void read(int &n)
 14 {
 15     char c='+';bool flag=0;n=0;
 16     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
 17     while(c>='0'&&c<='9')n=n*10+c-48,c=getchar();
 18 }
 19 struct node
 20 {
 21     int u,v,nxt;
 22 }edge[MAXN];
 23 int head[MAXN];
 24 int num=1;
 25 inline void add_edge(int x,int y)
 26 {
 27     edge[num].u=x;
 28     edge[num].v=y;
 29     edge[num].nxt=head[x];
 30     head[x]=num++;
 31 }
 32 struct T
 33 {
 34     int l,r,w,tag;
 35 }tree[MAXN];
 36 int n,k;
 37 int D[MAXN];
 38 int C[MAXN];
 39 int S[MAXN];
 40 int W[MAXN];
 41 int st[MAXN];
 42 int ed[MAXN];
 43 int dp[MAXN];// 修建了i个基站的费用 
 44 int ans;
 45 inline void update(int k)
 46 {
 47     tree[k].w=min(tree[ls].w,tree[rs].w);
 48 }
 49 inline void pushdown(int k)
 50 {
 51     if(!tree[k].tag)    return ;
 52     tree[ls].w+=tree[k].tag;
 53     tree[ls].tag+=tree[k].tag;
 54     tree[rs].w+=tree[k].tag;
 55     tree[rs].w+=tree[k].tag;
 56     tree[k].tag=0;
 57 }
 58 inline void Build_Tree(int k,int ll,int rr)
 59 {
 60     tree[k].tag=0;
 61     tree[k].l=ll;tree[k].r=rr;
 62     if(ll==rr)
 63     {
 64         tree[k].w=dp[ll];
 65         return ;
 66     }
 67     int mid=(ll+rr)>>1;
 68     Build_Tree(ls,ll,mid);Build_Tree(rs,mid+1,rr);
 69     update(k);
 70 }
 71 inline int query(int k,int ql,int qr)
 72 {
 73     if(tree[k].l==ql&&tree[k].r==qr)    
 74         return tree[k].w;
 75     pushdown(k);
 76     int mid=(tree[k].l+tree[k].r)>>1;
 77     if(qr<=mid)    return query(ls,ql,qr);
 78     else if(ql>mid)    return query(rs,ql,qr);
 79     else return min(query(ls,ql,mid),
 80                     query(rs,mid+1,qr));
 81 }
 82 inline void change(int k,int ql,int qr,int val)
 83 {
 84     if(tree[k].l==ql&&tree[k].r==qr)
 85     {
 86         tree[k].w+=val,tree[k].tag+=val;return ;
 87     }    
 88     pushdown(k);
 89     int mid=(tree[k].l+tree[k].r)>>1;
 90     if(qr<=mid)     change(ls,ql,qr,val);
 91     else if(ql>mid)    change(rs,ql,qr,val);
 92     else  
 93     {
 94         change(ls,ql,mid,val);
 95         change(rs,mid+1,qr,val);
 96     }
 97     update(k);
 98 }
 99 int main()
100 {
101     freopen("base.in","r",stdin);
102     freopen("base.out","w",stdout);
103     read(n);read(k);k++;
104     memset(head,-1,sizeof(head));
105     for(int i=2;i<=n;i++)    read(D[i]);
106     for(int i=1;i<=n;i++)    read(C[i]);
107     for(int i=1;i<=n;i++)    read(S[i]);
108     for(int i=1;i<=n;i++)    read(W[i]);
109     ++n;D[n]=W[n]=INF;
110     for(int i=1;i<=n;i++)
111     {
112         st[i]=lower_bound(D+1,D+n+1,D[i]-S[i])-D;
113         ed[i]=lower_bound(D+1,D+n+1,D[i]+S[i])-D;
114         if(D[ed[i]]>S[i]+D[i])    ed[i]--;
115         add_edge(ed[i],i);
116     }
117     
118     for(int i=1;i<=k;i++)
119     {
120         if(i==1)
121         {
122             int now=0;
123             for(int k=1;k<=n;k++)
124             {
125                 dp[k]=now+C[k];
126                 for(int j=head[k];j!=-1;j=edge[j].nxt)
127                 {
128                     //cout<<edge[j].v<<" "<<W[edge[j].v]<<endl;
129                     if(W[edge[j].v]==INF)continue;
130                     now+=W[edge[j].v];
131                 }
132                 
133             }
134             ans=dp[n];
135         }
136         else
137         {         
138             Build_Tree(1,1,n);int y;
139         //    for(int ii=1;ii<=10;ii++)
140         //        cout<<tree[ii].w<<" ";
141         //    cout<<endl;
142             for(int j=1;j<=n;j++)
143             {
144                 dp[j]= ((j>(i-1)) ? query(1,i-1,j-1) : 0 )+ C[j];
145                 for(int k=head[j];k!=-1;k=edge[k].nxt)
146                     if(st[y=edge[k].v]>1)
147                         change(1,1,st[y]-1,W[y]);
148             }
149             ans=min(ans,dp[n]);
150         }
151     }
152     printf("%d",ans);
153     return 0;
154 }

UKE

 

本代码来自:https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P2605


  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #define sL (s << 1)
  6 #define sR (s << 1 | 1)
  7 
  8 using namespace std;
  9 const int Maxn = 0x3f3f3f3f;
 10 const int N = 2e4 + 5, M = N << 2;
 11 int d[N], c[N], w[N], s[N], st[N], ed[N], f[N]; 
 12 int n, k, Ans, val[M], tag[M];
 13 
 14 struct point
 15 {
 16     int to; point *nxt;
 17 }a[M], *T = a, *lst[N]; 
 18 
 19 inline void addEdge(const int &x, const int &y) {T->nxt = lst[x]; T->to = y; lst[x] = T++;} 
 20 template <class T> inline T Min(const T &a, const T &b) {return a < b? a : b;}
 21 template <class T> inline void CkMin(T &a, const T &b) {if (a > b) a = b;}
 22 
 23 inline int get()
 24 {
 25     char ch; bool f = false; int res = 0;
 26     while (((ch = getchar()) < '0' || ch > '9') && ch != '-');
 27     if (ch == '-') f = true;
 28      else res = ch - '0';
 29     while ((ch = getchar()) >='0' && ch <= '9')
 30         res = (res << 3) + (res << 1) + ch - '0';
 31     return f? ~res + 1 : res;
 32 }
 33 
 34 inline void put(int x)
 35 {
 36     if (x < 0)
 37       x = ~x + 1, putchar('-');
 38     if (x > 9) put(x / 10);
 39     putchar(x % 10 + 48);
 40 }
 41 
 42 inline void Push(const int &s) {val[s] = Min(val[sL], val[sR]);}
 43 inline void Add(const int &s, const int &z) 
 44 {val[s] += z; tag[s] += z;}
 45 
 46 inline void Down(const int &s)
 47 {
 48     if (!tag[s]) return ;
 49     Add(sL, tag[s]); Add(sR, tag[s]); tag[s] = 0;
 50 }
 51 
 52 inline void Build(const int &s, const int &l, const int &r)
 53 {
 54     tag[s] = 0;
 55     if (l == r) return (void)(val[s] = f[l]);
 56     int mid = l + r >> 1;
 57     Build(sL, l, mid); Build(sR, mid + 1, r);
 58     Push(s);
 59 }
 60 
 61 inline int Query(const int &s, const int &l, const int &r, const int &x, const int &y)
 62 { 
 63     if (l == x && r == y) return val[s];
 64     Down(s); int mid = l + r >> 1; 
 65     if (y <= mid) return Query(sL, l, mid, x, y);
 66      else if (x > mid) return Query(sR, mid + 1, r, x, y);
 67       else return Min(Query(sL, l, mid, x, mid),
 68                          Query(sR, mid + 1, r, mid + 1, y));
 69 }
 70 
 71 inline void Modify(const int &s, const int &l, const int &r, const int &x, const int &y, const int &z)
 72 {
 73     if (l == x && r == y) return Add(s, z);
 74     Down(s); int mid = l + r >> 1;
 75     if (y <= mid) Modify(sL, l, mid, x, y, z);
 76      else if (x > mid) Modify(sR, mid + 1, r, x, y, z);
 77       else 
 78       {
 79           Modify(sL, l, mid, x, mid, z);
 80           Modify(sR, mid + 1, r, mid + 1, y, z);
 81       }
 82     Push(s);
 83 }
 84 
 85 int main()
 86 {
 87     n = get(); k = get() + 1;
 88     for (int i = 2; i <= n; ++i) d[i] = get();
 89     for (int i = 1; i <= n; ++i) c[i] = get();
 90     for (int i = 1; i <= n; ++i) s[i] = get();
 91     for (int i = 1; i <= n; ++i) w[i] = get();
 92     ++n; d[n] = w[n] = Maxn;  
 93     //当我们推导i时,我们只考虑了它和前面的基站产生的影响
 94     //这时对于最后一个基站我们不会考虑它和之后的村庄产生的影响
 95     //则我们可以在最后增加一个村庄
 96     //保证它必定被作为基站(无建设费用)且不对前面产生影响
 97     //这样就不会有遗漏的了 
 98     for (int i = 1; i <= n; ++i)
 99     {
100         st[i] = lower_bound(d + 1, d + n + 1, d[i] - s[i]) - d;
101         ed[i] = lower_bound(d + 1, d + n + 1, d[i] + s[i]) - d;
102         if (d[ed[i]] > d[i] + s[i]) ed[i]--; addEdge(ed[i], i);
103         //lower_bound查找的是大于等于x的第一个数
104         //而ed[i]要求的是小于等于x的最后一个数
105         //所以判断一下减一就可以了 
106     }
107     for (int i = 1; i <= k; ++i)
108     if (i == 1)
109     {
110         int res = 0;
111         for (int j = 1; j <= n; ++j)
112         {
113             f[j] = res + c[j];
114             for (point *e = lst[j]; e; e = e->nxt)
115              res += w[e->to];
116          }
117          Ans = f[n];
118     }
119     else 
120     {
121         Build(1, 1, n); int y;
122         for (int j = 1; j <= n; ++j)
123         {
124             //注意线段树区间的边界条件
125             f[j] = (j > i - 1 ? Query(1, 1, n, i - 1, j - 1) : 0) + c[j];
126             for (point *e = lst[j]; e; e = e->nxt)
127              if (st[y = e->to] > 1) Modify(1, 1, n, 1, st[y] - 1, w[y]);
128             //这里其实只要修改区间[i, st[y] - 1]就行了
129             //不过询问/修改的区间长对于线段树其实更快 
130         }
131         CkMin(Ans, f[n]);
132     }
133     return put(Ans), 0;
134 }

 

题解:

那题越发的幽默,完全虐翻了自己,初阶写的是没有优化的DP,T到40,原来正解就是这么些DP的优化,原DP中,定义的是 f[i][j] 表示第j个站安置在i那个职位的微乎其微费用,那里并不曾设想背后的基站,所以我们要新建二个点,且那一个点离开很远,开销为0,那样就可以圆满的联结答案到这么些点上边了,然后转移就是 f[i][j]=f[k][j-1]+c[k][i] ,c[k][i]表示k-i间覆盖不到的点的w总和.

设想优化:

困难在于求出c[k][i]其一东西,大家就考虑消掉那个事物,再思考会发现,j这一维是足以滚动的,大家就足以设想用线段树维护f[k][j-1],然后就是维护c这些东西,大家设st[i]为i左侧能覆盖到i的最远点,同理ed[i]为右侧最远点,那么一旦扫到了i,那么ed在i上边的点,并且只要转移是从st-1转移来的,那么这几个点就覆盖不到,就要在线段树[1,st[i]-1]的职位加上w[i],这样k的岗位就改成了f[k]+w[i]了,所以转移就是询问线段树[1,i-1]中的最小值

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define RG register
#define il inline
#define iter iterator
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define ls (node<<1)
#define rs (node<<1|1)
using namespace std;
typedef long long ll;
const int N=20005,M=105,inf=2e8;
int gi(){
    int str=0;char ch=getchar();
    while(ch>'9' || ch<'0')ch=getchar();
    while(ch>='0' && ch<='9')str=(str<<1)+(str<<3)+ch-48,ch=getchar();
    return str;
}
int n,m;int f[N],c[N],w[N],st[N],ed[N],Tree[N<<2],mark[N<<2];ll d[N],s[N];
int midl(int sta,ll x){
    int l=1,r=n,mid,ret=sta;
    while(l<=r){
        mid=(l+r)>>1;
        if(d[mid]>=x)ret=mid,r=mid-1;
        else l=mid+1;
    }
    return ret;
}
int midr(int sta,ll x){
    int l=1,r=n,mid,ret=sta;
    while(l<=r){
        mid=(l+r)>>1;
      if(d[mid]<=x)ret=mid,l=mid+1;
        else r=mid-1;
    }
    return ret;
}
int head[N],to[N],num=0,nxt[N];
void addedge(int x,int y){
    nxt[++num]=head[x];to[num]=y;head[x]=num;
}
void upd(int node){
    Tree[node]=Min(Tree[ls],Tree[rs]);
}
void build(int l,int r,int node){
    mark[node]=0;
    if(l==r){
        Tree[node]=f[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,ls);build(mid+1,r,rs);
    upd(node);
}
void pushdown(int node){
    if(!mark[node])return ;
    int k=mark[node];
    Tree[ls]+=k;Tree[rs]+=k;
    mark[ls]+=k;mark[rs]+=k;
    mark[node]=0;
}
void updata(int l,int r,int node,int sa,int se,int to){
    if(l>se || r<sa)return ;
    if(sa<=l && r<=se){
        Tree[node]+=to;mark[node]+=to;
        return ;
    }
    pushdown(node);
    int mid=(l+r)>>1;
    updata(l,mid,ls,sa,se,to);updata(mid+1,r,rs,sa,se,to);
    upd(node);
}
int query(int l,int r,int node,int sa,int se){
    if(l>se || r<sa)return inf;
    if(sa<=l && r<=se)return Tree[node];
    pushdown(node);
    int mid=(l+r)>>1;
    int q1=query(l,mid,ls,sa,se),q2=query(mid+1,r,rs,sa,se);
    upd(node);
    return Min(q1,q2);
}
void work()
{
    n=gi();m=gi();
    for(int i=2;i<=n;i++)d[i]=gi();
    for(int i=1;i<=n;i++)c[i]=gi();
    for(int i=1;i<=n;i++)s[i]=gi();
    for(int i=1;i<=n;i++)w[i]=gi();
    n++;d[n]=2e12;
    for(int i=1;i<=n;i++){
        st[i]=midl(i,d[i]-s[i]);ed[i]=midr(i,d[i]+s[i]);
        addedge(ed[i],i);
    }
    ll tot=0;
    for(int i=1;i<=n;i++){
        f[i]=tot+c[i];
        for(int j=head[i];j;j=nxt[j]){
            tot+=w[to[j]];
        }
    }
    ll ans=f[n];
    for(int j=2;j<=m+1;j++){
        build(1,n,1);
        for(int i=1;i<=n;i++){
            if(i>1)f[i]=query(1,n,1,1,i-1)+c[i];
            for(int k=head[i];k;k=nxt[k]){
                int u=to[k];
                if(st[u]>1)updata(1,n,1,1,st[u]-1,w[u]);
            }
        }
        ans=Min(ans,f[n]);
    }
    printf("%lld\n",ans);
}

int main()
{
    freopen("base.in","r",stdin);
    freopen("base.out","w",stdout);
    work();
    return 0;
}

相关文章