题目简介:有n组,每组有若干个蛇的蛇队伍。(也可以理解为n条长度若干的蛇。)我们要用网捕捉,中途可以改变网的大小。目标是浪费空间最小。
解法:首先明确方法:DP。设f[i][t]为捕捉了n条,变换了t次的最小浪费空间。直接求浪费可能稍显麻烦,但是 浪费空间+必要空间=总空间,所以说求浪费空间就直接用 总-必就行了。
那么什么是必要空间呢,即每条蛇的长度。要求一群蛇的总长度,就利用前缀和。
那什么是总空间呢?为了使空间最小,同时又能抓蛇,所以我们追求 刚好能抓 的情况,也就是 最大蛇长*蛇数。
预处理:一段范围内的最大值与前缀和
动态转移方程:f[i][t]=min(f[i][t],f[p][t-1]+maxx[p+1][i]*(i-p)-sum[i]+sum[p]);
p为枚举的,在第p条蛇变换后从p一直网到第i条的意义
代码
#include<iostream> #include<cstdio> #include<fstream> #include<cmath> #include<algorithm> #include<cstring> using namespace std; int read(){ char ch; int res=0,f=1; ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ res=res*10+(ch-'0'); ch=getchar(); } return res*f; } int u=1<<30; int n,k,a[405],f[405][405],maxn,sum[405],maxx[405][405]; int main(){ memset(f,127/3,sizeof(f)); n=read(); k=read(); for(int i=1;i<=n;++i){ a[i]=read(); maxn=max(maxn,a[i]); sum[i]=sum[i-1]+a[i]; maxx[i][i]=a[i]; } for(int i=1;i<=n;++i){ for(int j=i+1;j<=n;++j){ maxx[i][j]=max(maxx[i][j-1],maxx[j][j]); } } for(int i=1;i<=n-k;++i)f[i][0]=maxx[1][i]*i-sum[i]; for(int t=1;t<=k;++t){ for(int i=t+1;i<=n-(k-t);++i){ for(int p=t;p<i;++p){ f[i][t]=min(f[i][t],f[p][t-1]+maxx[p+1][i]*(i-p)-sum[i]+sum[p]); } } } printf("%d",f[n][k]); return 0; }