AcWing 1068. 环形石子合并
原题链接
简单
作者:
上班摸鱼中
,
2023-03-23 19:46:09
,
所有人可见
,
阅读 110
//同时求最小值和最大值,要用到两次dp
//注意:求最小值的时候,总是容易忘记一些初始化条件
//使得最小值恒为0!!!
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 410,INF = 1e9;
int n;
int s[N]; //存放前缀和
int a[N];//输入每个石头的重量
int f[N][N]; //存最大代价
int g[N][N]; //存最小代价
//集合含义:从i到j,合并石头的代价
//线性的1-n,共合并n-1次
int main(){
cin>>n;
//n变成2n
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[i+n] = a[i];
}
//求前缀和
for(int i=1;i<=2*n;i++)
{
s[i]=s[i-1]+a[i];
f[i][i] = g[i][i] = 0;
}
//枚举长度
for(int len=2;len<=n;len++)
{
for(int i=1;i+len-1<=2*n;i++)
{
int j=i+len-1;
//遍历i到j-1
g[i][j]=INF;//让这一段的最小值初始化为最大
f[i][j]=-INF;//最大值初始化为最小
for(int k=i;k<=j-1;k++)
{
g[i][j] = min(g[i][j],g[i][k]+g[k+1][j]+s[j]-s[i-1]);
f[i][j] = max(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
}
}
}
//g中的最小值 f中的最大值
int ans1 = 2e9,ans2=0;
for(int i=1;i<=n;i++){
ans1 = min(ans1,g[i][i+n-1]);
ans2 = max(ans2,f[i][i+n-1]);
}
cout<<ans1<<endl;
cout<<ans2<<endl;
return 0;
}