【Test】动态规划专题 [2]
写在前面
【概况】
时间四小时，总五题，写了三个题。
【时间分配】
看题花了很久(30min+)，总体上做题顺序 5->3->1(->4)。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。【问题】
1.抓不住动态规划状态的设置，每个阶段子结构之间的关系。
2.总是YY出一些奇奇怪怪能过样例的奇怪贪心。
3.一点也没用到这几天学的dp新姿势...
正文在此
t1
【问题描述】
有N棵小草，编号0至N-1。奶牛Bessie不喜欢小草，所以Bessie要用剪刀剪草，目标是使得这N棵小草的高度总和不超过H。在第0时刻，第i棵小草的高度是h[i]，接下来的每个整数时刻，会依次发生如下三个步骤：
（1）每棵小草都长高了，第i棵小草长高的高度是grow[i]。
（2）Bessie选择其中一棵小草并把它剪平，这棵小草高度变为0。注意：这棵小草并没有死掉，它下一秒还会生长的。
（3）Bessie计算一下这N棵小草的高度总和，如果不超过H，则完成任务，一切结束，否则轮到下一时刻。
你的任务是计算：最早是第几时刻，奶牛Bessie能完成它的任务？如果第0时刻就可以完成就输出0，如果永远不可能完成，输出-1，否则输出一个最早的完成时刻。
【输入】
第一行，两个整数N和H。 1 ≤ N ≤ 50，0 ≤ H ≤ 1000000。
第二行，N个整数，表示h[i]。0 ≤ h[i] ≤ 100000。
第三行，N个整数，表示grow[i]。1 ≤ grow[i] ≤ 100000。
【输出】
一个整数，最早完成时刻或-1。
【输入输出样例1】
| grass.in |
grass.out |
| 7 33 5 1 6 5 8 4 7 2 1 1 1 4 3 2 |
5 |
【做题过程】
首先一个假假假假的贪心，把每个时刻的小草中最高的拔掉，发现连样例都推不出来。
再是一个高级的假贪心。到了第i个时刻时，如果不考虑剪草操作，第j棵草的贡献将是p[j].h+i*p[j].g。
然后每次把贡献最高的减掉，每棵草的贡献分别减去g值，继续寻找最大值。
60分，代码如下：
![【Test】动态规划专题 [2] 随笔 第1张](https://img.liuyixiang.com/image/2019/5/nANvQn.gif "【Test】动态规划专题 [2] 随笔 第1张")
![【Test】动态规划专题 [2] 随笔 第2张](https://img.liuyixiang.com/image/2019/5/J3URJr.gif "【Test】动态规划专题 [2] 随笔 第2张")
//又是一个没有正确性的贪心 #include<bits/stdc++.h> using namespace std; #define ll long long #define File "grass" inline void file(){ freopen(File".in","r",stdin); freopen(File".out","w",stdout); } inline int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();} return x*f; } const int mxn = 55; int n,H; struct P{ ll h,g; bool v; }p[mxn],t[mxn]; inline bool cmp(P x,P y){ return x.h>y.h; } ll s_st(0),s_g(0); int main(){ file(); scanf("%d %d",&n,&H); for(int i = 1;i <= n; ++i) scanf("%d",&p[i].h),s_st += p[i].h; for(int i = 1;i <= n; ++i) scanf("%d",&p[i].g),s_g += p[i].g,p[i].v = 0; if(s_st <= H){ puts("0"); return 0; } int tot(0); while(++tot){ // printf("tot:%d\n",tot); ll sum = s_st; for(int i = 1;i <= n; ++i) t[i] = p[i],p[i].v = 0,t[i].v = 0; sum += s_g*tot; for(int i = 1;i <= n; ++i) p[i].h += 1ll*tot*p[i].g; for(int i = 1;i <= tot; ++i){ sort(p+1,p+n+1,cmp); sum -= p[1].h; p[1].v = 1; p[1].h = 0; // puts("**"); for(int j = 1;j <= n; ++j) if(p[j].v!=1) p[j].h -= p[j].g; } // printf("sum:%lld %d\n",sum,H); if(sum<=H){ printf("%d\n",tot); return 0; } for(int i = 1;i <= n; ++i) p[i] = t[i]; if(tot > 100000){ puts("-1"); return 0; } } return 0; } /* 7 33 5 1 6 5 8 4 7 2 1 1 1 4 3 2 */View Code
【题解大意】
由上面YY出来的贪心可以发现，选择删掉或者怎么删仿佛跟g有很大的关系。
先按照g从小到大排个序。
设f[i][j][k]为当前第i个时刻，枚举到第j棵小草，剪掉的小草为k个时 能剪掉的小草的最大高度值。
f[i][j][k] = max(f[i-1][j-1][k],f[i-1][j-1][k-1]+p[j].h+p[j].g*k);
【code】
#include<bits/stdc++.h> using namespace std; #define File "grass" #define ll long long inline void file(){ freopen(File".in","r",stdin); freopen(File".out","w",stdout); } inline int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();} return x*f; } const int mxn = 55; int n,H; struct P{ int h,g; friend bool operator <(P x,P y){ return x.g==y.g ? x.h<y.h : x.g<y.g; } }p[mxn]; int f[mxn][mxn]; int s_g(0),s_h(0); int main(){ file(); n = read(),H = read(); for(int i = 1;i <= n; ++i) p[i].h = read(),s_h += p[i].h; for(int i = 1;i <= n; ++i) p[i].g = read(),s_g += p[i].g; sort(p+1,p+n+1); if(s_h <= H){ puts("0"); exit(0); } for(int i = 1;i <= n; ++i){ int sum = s_h + s_g*i; memset(f,0,sizeof f); for(int j = 1;j <= n; ++j) for(int k = 1;k <= i; ++k) f[j][k] = max(f[j-1][k],f[j-1][k-1]+p[j].h+p[j].g*k); if(sum - f[n][i] <= H){ printf("%d\n",i); exit(0); } } puts("-1"); return 0; } /* 7 33 5 1 6 5 8 4 7 2 1 1 1 4 3 2 */View Code
讲题的时候ybc提出这个dp可以n^2解决，代码如下：
#include<bits/stdc++.h> using namespace std; #define File "grass" #define ll long long inline void file(){ freopen(File".in","r",stdin); freopen(File".out","w",stdout); } inline int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();} return x*f; } const int mxn = 55; int n,H; struct P{ int h,g; friend bool operator <(P x,P y){ return x.g==y.g ? x.h<y.h : x.g<y.g; } }p[mxn]; int f[mxn][mxn]; int s_g(0),s_h(0); int main(){ file(); n = read(),H = read(); for(int i = 1;i <= n; ++i) p[i].h = read(),s_h += p[i].h; for(int i = 1;i <= n; ++i) p[i].g = read(),s_g += p[i].g; sort(p+1,p+n+1); if(s_h <= H){ puts("0"); exit(0); } /* for(int i = 1;i <= n; ++i){ int sum = s_h + s_g*i; memset(f,0,sizeof f); for(int j = 1;j <= n; ++j) for(int k = 1;k <= i; ++k) f[j][k] = max(f[j-1][k],f[j-1][k-1]+p[j].h+p[j].g*k); if(sum - f[n][i] <= H){ printf("%d\n",i); exit(0); } }*/ for(int i = 1;i <= n; ++i) for(int j = 1;j <= i; ++j) f[i][j] = max(f[i-1][j],f[i-1][j-1]+p[i].h+p[i].g*j); for(int i = 1;i <= n; ++i) if(s_h + s_g*i - f[n][i] <= H){ printf("%d\n",i); exit(0); } puts("-1"); return 0; } /* 7 33 5 1 6 5 8 4 7 2 1 1 1 4 3 2 */View Code
t2
【问题描述】
现在有被划分为n个格子的一个圆环，每个格子上都有一个正整数，并且定义两个格子的距离为两个格子之间的格子数的最小值。
环的圆心处固定了一个指针，一开始指向了圆环上的某一个格子，你可以取下指针所指的那个格子里的数以及与这个格子距离小于k的格子的数，取一个数的代价即这个数的值。指针是可以转动的，每次转动可以将指针由一个格子转向其相邻的格子，且代价为圆环上还剩下的数的最大值。
对于给定的圆环和k，要求将所有数取完所有数的最小代价。
【输入】
输入文件的第1行有两个正整数n和k，描述了圆环上的格子数与取数的范围。
第2行有n个正整数，按顺时针方向描述了圆环上每个格子上的数，且指针一开始指向了第1个数字所在的格子。
所有整数之间用一个空格隔开，且不超过10000。
【输出】
输出文件仅包括1个整数，为取完所有数的最小代价。
【输入输出样例1】
| cirque.in |
cirque.out |
| 6 1 4 1 2 3 1 3 |
21 |
【样例说明】
如上图所示，第一步不转动指针，取走4、3两个数，代价为7； 第2步指针顺时针转动2格，圆环上最大数为3，代价为6，取走1、2、3三个数，代价为6； 第3步指针顺时针转动1格，代价为1，取走剩下的一个数1，代价为1； 最小代价为7+6+6+1+1=21。
【数据规模】
对于20%的数据，n≤10，k≤3；
对于40%的数据，n≤100，k≤10；
对于60%的数据，n≤500，k≤20；
【看题心理】
指针指来指去还在环上，看起来就是那种细节很多，调半个小时过了样例还wa得莫名其妙的题。
大概知道要贪心在指针指的第一个数附近尽量取，然后就把环变成了链，然后就可以区间dp?。
弃题弃题。。。
【题解大意】
好的，思路基本是对的。
首先预处理出区间[l~r]内的最大值(mx[l][r]数组)以方便后面转移，O(n^2)。
然后套路地枚举区间长度，枚举左端点位置。
设置状态f[i][j][0]表示在左端点更新，l到r的最小代价。
同理f[i][j][1]表示右端点...
想到是否处于边界位置只能向一边转移。
状态转移方程为:
f[l][r][0] = min(f[l][r][0],f[l][r][1]+(n-len-1-2*k)*mx[l][r]);
f[l][r][1] = min(f[l][r][1],f[l][r][0]+(n-len-1-2*k)*mx[l][r]);
【code】
#include<bits/stdc++.h> using namespace std; #define File "cirque" #define inf 1<<30 #define ll long long inline void file(){ freopen(File".in","r",stdin); freopen(File".out","w",stdout); } inline int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();} return x*f; } const int mxn = 2e3+5; int n,k; ll s(0); ll mn = inf; int a[mxn],mx[mxn][mxn]; ll f[mxn][mxn][2]; //0 left 1 right int main(){ // file(); n = read(),k = read(); for(int i = 1;i <= n; ++i) a[i] = read(),s = (ll)s+a[i]; for(int i = 1;i <= n; ++i){ mx[i][i] = a[i]; for(int j = i+1;j <= n; ++j) mx[i][j] = max(mx[i][j-1],a[j]); } memset(f,0x3f,sizeof f); f[k+2][n-k][0] = f[k+2][n-k][1] = 0; for(int len = n-k*2-2; len >= 0; --len){ for(int l = 1;l <= n-len+1; ++l){ int r = len+l-1; ll d = n-r+l-2-2*k; if(l>1) f[l][r][0] = min(f[l-1][r][0] + mx[l-1][r], f[l-1][r][1] + 1ll*d*mx[l-1][r]); if(r<n) f[l][r][1] = min(f[l][r+1][1] + mx[l][r+1], f[l][r+1][0] + 1ll*d*mx[l][r+1]); f[l][r][0] = min(f[l][r][0],f[l][r][1]+1ll*d*mx[l][r]); f[l][r][1] = min(f[l][r][1],f[l][r][0]+1ll*d*mx[l][r]); } } for(int i = 2;i <= n; ++i) mn = min(min(mn,f[i][i-1][0]),f[i][i-1][1]); printf("%lld\n",mn+s); return 0; } /* 6 1 4 1 2 3 1 3 */View Code
t3
【问题描述】
给一棵n 个结点的有根树，结点由1 到n 标号，根结点的标号为1。每个结点上有一个物品，第i 个结点上的物品价值为vi。
你需要从所有结点中选出若干个结点，使得对于任意一个被选中的结点，其到根的路径上所有的点都被选中，并且选中结点的个数不能超过给定的上限lim。在此前提下，你需要最大化选中结点上物品的价值之和。
求这个最大的价值之和。
【输入】
第一行为两个整数n; lim
接下来n 行，第i 行包含一个整数vi，表示结点i 上物品的价值。
接下来n- 1 行，每行包含两个整数u; v, 描述一条连接u; v 结点的树边。
【输出】
输出一行答案。
【输入输出样例1】
| tree.in |
tree.out |
| 6 4 -5 4 -6 6 9 6 3 2 3 1 2 4 2 5 1 6 |
2 |
【数据范围】
对于前20% 的数据，1<=n; lim<=10
对于前60% 的数据，1<=n; lim<=100
对于100% 的数据，1<=n; lim<=3000; |vi| <=10^5 数据有梯度，保证给出的是合法的树。
【做题过程】
看题的时候的标注上了树上背包dp，好，是道能好好写的题。
然后开始推式子，大概想的是：
f[i][j]表示选取第i号节点，已经选了j个节点的最大花费。
f[y][k] =max(f[y][k]，f[x][k-1]+w[y]);
其中第二维，因为从根节点到当前节点的路径上的点全部都要选取，所以预先处理了deep值，然后从lim到deep倒叙循环。
调了一会儿过了样例，但是只有10分我震惊。
代码如下：
//树上背包dp #include<bits/stdc++.h> using namespace std; #define ll long long #define File "tree" inline void file(){ freopen(File".in","r",stdin); freopen(File".out","w",stdout); } inline int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();} return x*f; } const int mxn = 3e3+5; int n,lim; struct edge{ int nxt,y; }e[mxn<<1]; int to[mxn],len; inline void add(int xx,int yy){ e[++len].nxt = to[xx]; to[xx] = len; e[len].y = yy; } int f[mxn][mxn],w[mxn]; bool v[mxn]; int d[mxn]; //处理深度值 inline void dfs(int x){ v[x] = 1; for(int i = to[x]; i;i = e[i].nxt){ int y = e[i].y; if(v[y]) continue; dfs(y); d[y] = d[x]+1; } } inline void dp(int x){ v[x] = 1; for(int i = to[x]; i;i = e[i].nxt){ int y = e[i].y; if(v[y]) continue; if(d[y]>lim) continue; // dp(y); for(int j = lim; j > d[y]; --j) f[y][j] = max(f[x][j-1]+w[y],f[y][j]); dp(y); } } int main(){ file(); n = read(),lim = read(); for(int i = 1;i <= n; ++i) w[i] = read(); for(int i = 1;i < n; ++i){ int u = read(),v = read(); add(u,v),add(v,u); } memset(f,0xcf,sizeof f); f[1][1] = w[1]; for(int i = 1;i <= n; ++i) f[i][0] = 0; dfs(1); memset(v,0,sizeof v); dp(1); int ans = 0; for(int i = 1;i <= n; ++i) for(int j = 0;j <= lim; ++j) ans = max(ans,f[i][j]); // puts(""); printf("%d\n",ans); return 0; } /* 6 4 -5 4 -6 6 9 6 3 2 3 1 2 4 2 5 1 6 */View Code
【题解大意】
其实前面的那个dp状态的设置是对的。虚神好像也是这么写的但是写出来也只有10分。
问题在于状态方程的转移。全场只有fcy一个人是O(n^2)的树形dp跑过去的，其余的满分都是用O(n^3)水的。
由于O(n^3)就能苟过去我没写O(n^2)的。
O(n^3)代码如下：
#include<bits/stdc++.h> using namespace std; #define File "tree" #define ll long long inline void file(){ freopen(File".in","r",stdin); freopen(File".out","w",stdout); } inline int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();} return x*f; } const int mxn = 3e3+5; int n,lim; int w[mxn],f[mxn][mxn],sz[mxn]; struct edge{ int y,nxt; }e[mxn<<1]; int to[mxn],len; inline void add(int xx,int yy){ e[++len].nxt = to[xx]; to[xx] = len; e[len].y = yy; } inline void dfs(int x,int fa){ sz[x] = 1; for(int i = lim;i >= 1; --i) f[x][i] = f[x][i-1]+w[x]; for(int i = to[x]; i;i = e[i].nxt){ int y = e[i].y; if(y==fa) continue; dfs(y,x); sz[x] += sz[y]; for(int j = lim;j >= 1; --j) for(int k = 1;k <= min(sz[y],j-1); ++k) f[x][j] = max(f[x][j],f[x][j-k]+f[y][k]); } } int main(){ file(); n = read(),lim = read(); for(int i = 1;i <= n; ++i) w[i] = read(); for(int i = 1;i < n; ++i){ int x = read(),y = read(); add(x,y),add(y,x); } // memset(f,0xcf,sizeof f); dfs(1,0); printf("%d\n",f[1][lim]); return 0; } /* /* s[x]=1; for(int j=m;j>=1;--j) f[x][j]=f[x][j-1]+v[x]; for(int i=lin[x];i;i=e[i].nxt) { int y=e[i].y; if(y==fa)continue; dfs(y,x); s[x]+=s[y]; for(int j=m;j>=1;--j) for(int k=1;k<=min(s[y],j-1);++k) f[x][j]=max(f[x][j],f[x][j-k]+f[y][k]); } } */ /* 6 4 -5 4 -6 6 9 6 3 2 3 1 2 4 2 5 1 6 */View Code
fcy若干年前关于树形dp的一篇博客，可以把很多O(n^3)的树形dp都变成O(n^2)的。
瓜皮太强啦。
具体说说O(n^2)的最优解变成了10分挂在哪里。
首先是再看之前列的状态转移方程：
f[y][k] =max(f[y][k]，f[x][k-1]+w[y]);
从跟节点开始dfs那么显然到x节点的时候y节点是没有更新到的，所以f[y][k]还是0（这里是我出错的原因
所以先将f[y][k]赋值为f[x][k-1]+w[y]，等处理完之后再f[x][k] = max(f[x][k],f[y][j])一遍更新即可。
但是这样的代码只有20分，如下：
#include<bits/stdc++.h> using namespace std; #define File "tree" #define ll long long inline void file(){ freopen(File".in","r",stdin); freopen(File".out","w",stdout); } inline int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();} return x*f; } const int mxn = 3e3+5; int n,lim; int w[mxn],f[mxn][mxn],sz[mxn]; struct edge{ int y,nxt; }e[mxn<<1]; int to[mxn],len; inline void add(int xx,int yy){ e[++len].nxt = to[xx]; to[xx] = len; e[len].y = yy; } inline void dfs(int x,int fa){ for(int i = to[x]; i;i = e[i].nxt){ int y = e[i].y; if(y==fa) continue; for(int j = 1;j <= lim; ++j) f[y][j] = f[x][j-1]+w[y]; dfs(y,x); for(int j = 1;j <= lim; ++j) f[x][j] = max(f[x][j],f[y][j]); } } int main(){ file(); n = read(),lim = read(); for(int i = 1;i <= n; ++i) w[i] = read(); for(int i = 1;i < n; ++i){ int x = read(),y = read(); add(x,y),add(y,x); } f[1][1] = w[1]; dfs(1,0); int ans = 0; for(int i = 1;i <= lim; ++i) ans = max(ans,f[1][i]); printf("%d\n",ans); return 0; } /* 6 4 -5 4 -6 6 9 6 3 2 3 1 2 4 2 5 1 6 */View Code
仔细观察了瓜皮的代码，发现枚举边的时候要倒序循环？。
【code】
#include <bits/stdc++.h> using namespace std; int n,lim,ip1,ip2,ans; int v[3050]; vector<int>Link[3050]; int f[3050][3050]; int dfs(int x,int fa){ for (int i=Link[x].size()-1;i>=0; --i) if(Link[x][i]!=fa){ for (int j=1;j<=lim;++j) f[Link[x][i]][j]=f[x][j-1]+v[Link[x][i]]; dfs(Link[x][i],x); for (int j=1;j<=lim;++j) f[x][j]=max(f[x][j],f[Link[x][i]][j]); } } int main(){ // freopen("tree.in","r",stdin); // freopen("tree.out","w",stdout); memset(f,-0x3f,sizeof(f)); scanf("%d%d",&n,&lim); for (int i=1;i<=n;++i) scanf("%d",&v[i]); for (int i=1;i<n;++i){ scanf("%d%d",&ip1,&ip2); Link[ip1].push_back(ip2); Link[ip2].push_back(ip1); } f[1][1]=v[1]; dfs(1,0); for (int i=1;i<=lim;++i) ans=max(ans,f[1][i]); printf("%d",ans); return 0; }View Code
t4
【问题描述】
机房最近决定举行一场锦标赛。锦标赛共有N个人参加，共进行N-1轮。第一轮随机挑选两名选手进行决斗，胜者进入下一轮的比赛，第二轮到第N-1轮再每轮随机挑选1名选手与上一轮胜利的选手决斗，最后只剩一轮选手。第i名选手与第j名选手决斗，第i名选手胜利的概率是a[i][j].
作为一号选手的小x想知道如何安排每轮出场的选手可以使得他获胜的概率最大，并求出这个最大概率。
【输入】
第一个一个整数N，表示参赛人数。
接下来N行，每行N个小数表示a[i][j]
保证满足a[i][i]=0，a[i][j]+a[j][i]=1；
【输出】
一个小数，表示最大概率。与答案误差不超过10^(-5) 即算正确。
【输入输出样例1】
| combat.in |
combat.out |
| 3 0.0 0.5 0.8 0.5 0.0 0.4 0.2 0.6 0.0 |
0.6800000 |
样例解释
第一轮2与3决斗，胜者与1决斗
如果2获胜，那么最后1获胜的概率为a[2][3]*a[1][2]=0.2
如果3获胜，那么最后1获胜的概率为a[3][2]*a[1][3]=0.48
所以总概率为0.68
【数据范围】
对于30%的数据，N<=10
对于60%的数据，N<=15
对于100%的数据，N<=18
【看题过程】
数据范围疯狂暗示这是个状压dp，但是我不是很会状压，考场上是不是可以偷偷放一放，有多的时间慢慢写。
【题解大意】
状压dp。
f[s]表示集合s时1获胜的概率。
需特别注意这里数组都要从0为下标开始。
具体实现看代码。
【code】
#include<bits/stdc++.h> using namespace std; #define File "combat" #define ll long long #define ull unsigned long long inline void file(){ freopen(File".in","r",stdin); freopen(File".out","w",stdout); } const int mxn = 20; int n; double f[1<<mxn],a[mxn][mxn]; int main(){ // file(); scanf("%d",&n); for(int i = 0;i < n; ++i) for(int j = 1;j < n; ++j) cin >> a[i][j]; f[1] = 1.0; for(int s = 1; s < (1<<n); ++s){ for(int i = 0;i < n; ++i){ if(s>>i&1){ for(int j = 0;j < n; ++j) if(s>>j&1) f[s] = max(f[s], f[s^(1<<i)] * a[j][i] + f[s^(1<<j)] * a[i][j]); } } } printf("%.7f\n",f[(1<<n)-1]); return 0; } /* 3 0.0 0.5 0.8 0.5 0.0 0.4 0.2 0.6 0.0 */View Code
t5
【问题描述】
我们需要将一个文件复制到n个服务器上，这些服务器的编号为S1, S2, …, Sn。
首先，我们可以选择一些服务器，直接把文件复制到它们中；将文件复制到服务器Si上，需要花费ci > 0的置放费用。对于没有直接被复制文件的服务器Si来说，它依次向后检查Si+1, Si+2, …直到找到一台服务器Sj：Sj中的文件是通过直接复制得到的，于是Si从Sj处间接复制得到该文件，这种复制方式的读取费用是j – i（注意j>i）。另外，Sn中的文件必须是通过直接复制得到的，因为它不可能间接的通过别的服务器进行复制。我们设计一种复制方案，即对每一台服务器确定它是通过直接还是间接的方式进行复制（Sn只能通过直接方式），最终使每一台服务器都得到文件，且总花费最小。
【输入】
输入文件的第一行有一个整数n，表示服务器的数目。
输入文件的第二行有n个整数，顺数第i个表示ci：在Si上直接复制文件的费用。
【输出】
输出文件中只包含一个整数，即最少需要花费的费用。
【输入输出样例1】
| server.in |
server.out |
| 10 2 3 1 5 4 5 6 3 1 2 |
18 |
【数据范围】
60%的数据中，1 <= n <= 1 000
100%的数据中，1 <= n <= 1 000 000
80%的数据中， 1 <= ci <= 50
100%的数据中，1 <= ci <= 1 000 000 000
最终结果可能较大，请注意选择适当的数据类型进行计算。
【做题过程】
很快YY出一个dp，大概知道要用斜率优化，脑抽60分的O(n^2)，被我每次用一个数组记录最优解由什么转移而来，优化成O(n)，只有20分。
代码如下：
#include<bits/stdc++.h> using namespace std; #define ll long long #define File "server" inline void file(){ freopen(File".in","r",stdin); freopen(File".out","w",stdout); } inline int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();} return x*f; } const int mxn = 1e6+5; int n; int c[mxn],f[mxn][2]; int main(){ // file(); n = read(); for(int i = 1;i <= n; ++i) c[i] = read(); memset(f,0x3f,sizeof f); f[n][1] = f[n][0] = c[n]; for(int i = n-1; i; --i){ for(int j = i+1;j <= n; ++j) f[i][0] = min(f[i][0],f[j][1]+(j-i+1)*(j-i)/2);//间接复制 f[i][1] = min(f[i+1][1],f[i+1][0]) + c[i];//直接复制 } printf("%d\n",min(f[1][1],f[1][0])); return 0; } /* 4 3 10 2 4 10 2 3 1 5 4 5 6 3 1 2 */View Code
【题解大意】
暴力dp是这样的：
直接复制:f[i][1] = min(f[i+1][0],f[i+1][1])+c[i];
间接复制:f[i][0] = min(f[i][0],f[j][1]+(j-i+1)*(j-i)/2); (i+1 <= j <= n)
f[n][1] = c[n],其余赋值为正无穷。
然后考虑如何对间接复制的方程进行斜率优化，推式子跟之前的几篇博客差不多吧，都是套路。
【code】
#include<bits/stdc++.h> using namespace std; int N,Head=1,Tail=0,Q[1000010]={}; long long C[1000010]={},F[1000010][2]={}; long long Val(int x){ return F[x][0]+((long long)x+1)*x/2; } double Calc(int x,int y){ return (Val(x)-Val(y))*1.0/(x-y); } int main(){ scanf("%d",&N); for(int i=1;i<=N;i++) scanf("%lld",&C[i]); for(int i=1;i<=N;i++) F[i][0]=222222222222; F[N][0]=C[N]; F[N][1]=222222222222; Q[++Tail]=N; // printf("%d\n",Tail); for(int i=N-1;i>=1;i--){ F[i][0]=min(F[i+1][0],F[i+1][1])+C[i]; for(;Head+1<=Tail&&Calc(Q[Head],Q[Head+1])>=i;Head++); F[i][1]=F[Q[Head]][0]+((long long)Q[Head]-i+1)*(Q[Head]-i)/2; for(;Head+1<=Tail&&Calc(Q[Tail],i)>Calc(Q[Tail-1],Q[Tail]);Tail--); Q[++Tail]=i; printf("l,r:%d %d\n",Head,Tail); printf("f[i][0]:%d f[i][1]:%d\n",F[i][0],F[i][1]); } printf("%lld\n",min(F[1][0],F[1][1])); return 0; }View Code
