题解 P1880 【[NOI1995]石子合并】
经典的区间DP
题目传送门
看到这道题我第一眼想到DP和贪心。 但必须要相邻的才能合并，所以果断选择DP；
1. 读入
这道题就是一个断环为链的操作，如果输入的为x1,x2,x3,…… x2,那么我们把xn+1赋值为x1，xn+2赋值为x2，……,xn+n赋值为xn;
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[i+n]=a[i];
}那我们就会发现从x1到x 2*n就是一个环，我们可以理解成环上的DP
-
状态转移 把当前阶段的合并方法细分成前一阶段已计算出的方法，选择其中的最优方案
for(int i=1;i<=n;i++) { for(int l=1;l+i<=2*n;l++) { int r=l+i-1; for(int mid=l;mid<r;mid++) { Max[l][r]=max(Max[l][mid]+Max[mid+1][r]+w[r]-w[l-1],Max[l][r]); Min[l][r]=min(Min[l][mid]+Min[mid+1][r]+w[r]-w[l-1],Min[l][r]); } } }
- 优化
为了防止自己合并自己，我们可以将这种可能赋值为0，即使自己合并自己，也不会有结果；
for(int i=1;i<=2*n;i++)
{
w[i]=w[i-1]+a[i];
} - 输出
这题是求最大值和最小值。我们可以过一遍Max和Min两个数组，打擂求出答案
int ans=0,ans1=0x7f7f7f7f;//最大值和最小值
for(int i=1;i<=n;i++)
{
ans=max(ans,Max[i][i+n-1]);
ans1=min(ans1,Min[i][i+n-1]);
}
cout<<ans1<<endl<<ans;