题目链接
题目描述
传说，数千年前圣帕特里克消灭了哞尔兰所有的蛇。然而，蛇们现在卷土重来了！圣帕特里克节是在每年的3月17日，所以Bessie要用彻底清除哞尔兰所有的蛇来纪念圣帕特里克。
Bessie装备了一个捕网，用来捕捉 N 组排成一行的蛇（1≤N≤400 ）。Bessie必须按照这些组在这一行中出现的顺序捕捉每一组的所有蛇。每当Bessie抓完一组蛇之后，她就会将蛇放在笼子里，然后带着空的捕网开始捕捉下一组。
一个大小为 s 的捕网意味着Bessie可以抓住任意包含 g 条的一组蛇，其中 g≤s 。然而，每当Bessie用大小为 s 的捕网抓住了一组 g 条蛇，就意味着浪费了 s−g 的空间。Bessie可以任意设定捕网的初始大小，并且她可以改变 K 次捕网大小（1≤K<N ）。
请告诉Bessie她捕捉完所有组的蛇之后可以达到的总浪费空间的最小值。
题目分析
这道题是一道比较明显的DP。我们首先来考虑一个特例——对于一个区间，如果只能设定捕网大小一次，那么需要设定的捕网大小即为区间内最大组的大小，而浪费的空间即为最大值与组数乘积再减去组内所使用的空间之和。那么当可以设定n次时，我们枚举区间中间的一个点，使它作为改变第n次的点，改变这一次的策略便与上面一样唯一确定了，而改变这一次之前的情况则已经计算过了。
这样，设fi,j为前i组改变j次捕网大小所浪费的最小空间，根据上面的推论，
fi,0=maxof(1,i)*i-sum(1,i)，fi,j=max{fl,j-1+maxof(l+1,i)*(i-l)-sum(l+1,i)}(j≠0,j-1<=l<i)。
代码
1 #include<algorithm> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 int n,k,a[401],f[401][401],maxof[401][401],sum[401]; 6 int main() 7 { 8 scanf("%d%d",&n,&k); 9 for(int i=1;i<=n;++i) 10 { 11 scanf("%d",&a[i]); 12 sum[i]=sum[i-1]+a[i]; 13 maxof[i][i]=a[i]; 14 } 15 for(int i=1;i<=n;++i) 16 for(int j=i+1;j<=n;++j) 17 maxof[i][j]=max(maxof[i][j-1],a[j]); 18 memset(f,0x7f/3,sizeof f); 19 for(int i=1;i<=n;++i) 20 f[i][0]=maxof[1][i]*i-sum[i]; 21 for(int i=1;i<=n;++i) 22 for(int j=1;j<=min(i,k);++j) 23 for(int l=j;l<i;++l) 24 f[i][j]=min(f[i][j],f[l][j-1]+maxof[l+1][i]*(i-l)-sum[i]+sum[l]); 25 printf("%d",f[n][k]); 26 return 0; 27 }