区间DP+环形处理
思路
把环形转化成链状即可,具体操作方法:将数组复制一倍到原数组后面形成一个长度为2n的新数组
其他思路和我之前链状的石子合并DP题解一样,不过细节上还是有些小区别
代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e2+10;
int n,f1[N][N],a[N],f2[N][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<=2*n;i++)
a[i]+=a[i-1];
for(int len=1;len<=n-1;len++)//顺带一提我这样循环遍历直接避开了i=j的情况,由于f[i][i]=0所以也不需要考虑
for(int i=1;i+len<=2*n;i++)//循环细节点1:i+len<=2*n
{
int j=i+len;
f1[i][j]=INT_MAX;
f2[i][j]=INT_MIN;
for(int k=0;k<len;k++)
{
f1[i][j]=min(f1[i][j],f1[i][i+k]+f1[i+k+1][j]+a[j]-a[i-1]);
f2[i][j]=max(f2[i][j],f2[i][i+k]+f2[i+k+1][j]+a[j]-a[i-1]);
}
}
int res_min=INT_MAX;
int res_max=INT_MIN;
for(int i=1;i<=n;i++)//还有这个循环选取答案,链状是直接输出f[1][n]
{
res_min=min(res_min,f1[i][i+n-1]);
res_max=max(res_max,f2[i][i+n-1]);
}
cout<<res_min<<endl;
cout<<res_max<<endl;
return 0;
}