题目
题解
这是一道经典的区间dp题，f[l][r]表示将区间[l,r]之间的石子合并后的最值。可以由长度小的区间推得长度大的区间的信息。题中数据是环状的，需要断环为链，将原序列复制并加到后面。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include <bits/stdc++.h> using namespace std; const int inf=0x7fffffff; const int maxn=200+5; int n; int f1[maxn][maxn],f2[maxn][maxn],a[maxn],sum[maxn]; //sum[]是前缀和,f1,f2[][]分别表示最小/大值 inline void dp() { for(int i=1;i<=(n<<1);i++)for(int j=i+1;j<=(n<<1);j++) f1[i][j]=inf,f2[i][j]=-inf; for(int len=2;len<=n;len++) //区间长度 { for(int l=1; ;l++) //区间左端点 { int r=l+len-1; if(r>(n<<1)) break; for(int k=l;k<r;k++) //枚举断点 { f1[l][r]=min(f1[l][r],f1[l][k]+f1[k+1][r]+sum[r]-sum[l-1]); f2[l][r]=max(f2[l][r],f2[l][k]+f2[k+1][r]+sum[r]-sum[l-1]); } } } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) {scanf("%d",&a[i]); a[i+n]=a[i];} for(int i=1;i<=(n<<1);i++) sum[i]=sum[i-1]+a[i]; dp(); int ans_min=inf,ans_max=-inf; for(int l=1; ;l++) { if(l>n+1) break; ans_min=min(ans_min,f1[l][l+n-1]); ans_max=max(ans_max,f2[l][l+n-1]); } printf("%d\n%d\n",ans_min,ans_max); return 0; } |
【小白解析】
此题解法较简明易懂。需注意f1/f2[l][r]代表合并[l,r]区间完毕后的最小/最大值，故18和19行的操作中，+sum[r]-sum[l-1]的造作本意是将已经合并完成的[l,k]和[k+1,r]所累积的分数，再加上合并这两堆的分数。
*话说第4行的200+5究竟是个啥啊……
200是序列长度的两倍，5是随便加
为毛不直接写205啊（恼）