我发现上一阵子来我做事总是非常荒诞
我连一条链上的区间dp都没做 就去做环上的区间dp 唉 半小时才调过
那么这一题的大意就是
在一个环上有n个点
每一个点都对应有一个权值
每一次你可以把这个环上相邻的两个点合并起来
合并起来消耗的代价就是两个点的权值之和
两个点合并之后就变成了一个点
问把所有的点合并成同一个点的最大花费和最小花费
那么这一道题首先肯定不能用贪心
如果使用贪心 必须是把不必相邻的两个点合并
这才能用贪心来做
那么这一道题是一个区间dp
区间dp就是我们在一条链上进行dp
枚举一个个区间的左端点和右端点
区间dp还要枚举一个k
是这个区间的中间的分割点
我们在进行状态转移的时候就是以这个k点为分割点
把k点左右的两个小区间进行合并处理
所以我们的状态转移方程就是
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+sum[j]-sum[i-1])
那个sum是预处理出来的前缀和
这一道题难道就这么轻松地解决了吗
不是的
这一道题是在一个环上进行的操作
如果我们还想要用区间dp来求解这一道题 我们需要把环转化为链
有两种方式
第一种方式 也是比较好理解的 我们枚举从1-n从那个地方把这个环断开变成链
第二种方式 实现起来比较简单 就是我们把这个环n个点复制一遍加在后面
比如样例是4 5 9 4
我们就变成 4 5 9 4 4 5 9 4
这就是传说中的断环为链
我们这里采用的是第二种方式
我们来解释一下第二种方式是如何实现的
我们把最外层循环改成区间的长度
从2-n（毕竟1就没有什么意义了）枚举
第二层循环是l 也就是区间的左端点
从1-(2*n-len+1)
那么怎么确定右端点呢 其实还是非常显然的
r=l+len-1
第三层循环还是枚举k
这样子我们在进行dp的过程中
这个区间有一些是跨过了第n个点的 到达了第n个点之后的位置
这样子其实就相当于把环转化为了链（仔细想一想啊 只可意会不可言传）
到最后的时候我们只需要把所有的长度为n的区间的值求一个最大或者最小就行了
具体看代码鸭（我太难了）
//P1880 [NOI1995]石子合并 #include<bits/stdc++.h> #define maxn 305 using namespace std; int a[maxn]; int f[maxn][maxn],dp[maxn][maxn]; int sum[maxn]; int main() { memset(dp,0x3f,sizeof(dp)); int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i+n]=a[i],dp[i+n][i+n]=dp[i][i]=0; for(int i=1;i<=n*2;i++) sum[i]=sum[i-1]+a[i]; for(int len=2;len<=n;len++) for(int i=1;i<=2*n-len+1;i++) { int j=i+len-1; for(int k=i;k<j;k++) { dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]); f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+sum[j]-sum[i-1]); } } int Max=-1,Min=0x3f3f3f3f; for(int i=1;i<=n;i++) Max=max(Max,f[i][i+n-1]),Min=min(Min,dp[i][i+n-1]); cout<<Min<<endl<<Max; return 0; }