环形石子合并
题目 环形石子合并
思路分析
在之前那题的基础上加上了个环形 以及最大花费
环形相邻 情况已经碰到很多次了
把链延长两倍，变成 2n，其中 i和 i+n是相同的两个堆，然后直接套 区间DP 模板
状态表示—集合\(f_{en,l,r}\)：当前合并的石子堆的大小为 len，且石子堆的左端点是 l，右端点是 r的方案
状态表示—属性\(f_{len,l,r}\)：方案的费用最大/最小（本题两者都要求）
状态计算—\(f_{len,l,r}\):
初始状态： \(f_{1,i,i}(1≤i≤n)\)
目标状态：\(f_{n,1,n}\)
len这一维的空间可以省去因为 r−l+1=len，也就保证了在已知 l和 r的情况下，不会出现状态定义重复的情况
这俩题都是基于 相邻两堆石子俩俩合并的 所以用区间dp 如果是任意两堆或者多堆合并 就用贪心
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=210,M=N*2,INF=0x3f3f3f3f;
int a[M],s[M];
int f[M][M],g[M][M];
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i+n]=a[i];
}
for(int i=1;i<=n*2;i++)
s[i]=s[i-1]+a[i];
memset(f,0x3f,sizeof f);//求最小 初始化inf
memset(g,-0x3f,sizeof g);//求最大 初始化-inf
for(int len=1;len<=n;len++){ // 枚举区间长度
for(int i=1;i+len-1<=n*2;i++){// 枚举起点
int j=i+len-1;//计算终点
if(len==1){//最小区间特判
f[i][j]=g[i][j]=0;
continue;
}
for(int k=i;k<=j-1;k++){// 枚举分割点，构造状态转移方程
//k只能在一边 类似于二分的划法 一般把k放左边 k+1为右区间起点
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
g[i][j]=max(g[i][j],g[i][k]+g[k+1][j]+s[j]-s[i-1]);
}
}
}
//目标状态中找出方案 因为是环形 所以不能直接1-n 而是在所以1-n长度中找max/min
int minv = INF, maxv = -INF;
for (int l = 1; l <= n; ++ l){
minv = min(minv, f[l][l + n - 1]);
maxv = max(maxv, g[l][l + n - 1]);
}
printf("%d\n%d\n", minv, maxv);
return 0;
}
💬 评论