环形石子合并
石子合并为区间dp的母题,下面着重讲一下区间dp的注意事项:
状态定义:f[i, j]定义为左端点为i,右端点为j的区间合并所需要的最小代价。
状态转移:f[i, j]=min(f[i, j], f[i, k]+f[k+1, j]+s[j]-s[i-1])
下面讲一下状态转移中的一些注意事项:
- 这里面的k是区间断点,表示左区间的右端点,为了保证右区间有意义,我们需要让k+1<=j,所有在转移时,我们遍历k从i到j-1
- s数组为前缀和数组,详细见前缀和的模板
区间问题的dp数组更新时,使用以下模板:
for (int len = 1; len <= n; len++) // 区间长度,从len=1开始遍历
for (int i = 1; i + len - 1 <= n; i++) { // 枚举起点
int j = i + len - 1; // 区间终点
if (len == 1) dp[i][j] = 初始值
else{
for (int k = i; k < j; k++) { // 枚举分割点,构造状态转移方程
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i][j]);
}
}
}
下面来介绍一下环形的区间如何解决,我们选择把原来的石子数组复制一次接在原数组的后面,我们做一次区间dp预处理好这个2*n大小的dp数组,然后最后直接遍历1到n,每次取minv=min(minv,f[i, i+n])即可,这样可以在较低的复杂度完成这一工作。
#include<iostream>
#include<cstring>
using namespace std;
const int N = 210,M=N<<1;
int n;
int a[M],s[M];
int f[M][M],g[M][M];
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<<1;i++){
s[i]=s[i-1]+a[i];
}
memset(f,0x3f,sizeof f);
memset(g,-0x3f,sizeof g);
for(int len=1;len<=n;len++){
for(int i=1;i+len-1<=n<<1;i++){
int j=i+len-1;
if(len==1)f[i][j]=g[i][j]=0;
else {
for(int k=i;k+1<=j;k++){
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]);
}
}
}
}
int maxv=-0x3f3f3f3f,minv=0x3f3f3f3f;
for(int i=1;i<=n;i++){
maxv=max(maxv,g[i][i+n-1]);
minv=min(minv,f[i][i+n-1]);
}
cout<<minv<<endl<<maxv<<endl;
return 0;
}