题目描述
有n堆环形摆放的石子使他们合并成一堆所得到的最大/最小得分
思路
由于题中说了是环形我们可以很自然的想到使他们变成两段转换成普通的线性方式求解,由于题目说了是合并相邻两堆则他必然是从小区间转换成大区间故用区间dp可以解决
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=410;
LL f[N][N],a[N];
int main()
{
ios::sync_with_stdio(false);
int n;
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=2;len<=n;len++)
{
for(int i=1;i+len-1<=2*n;i++)
{
int j=i+len-1;
for(int k=i;k<j;k++) f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+a[j]-a[i-1]);
}
}
LL ma=0;
for(int i=1;i<=n;i++) ma=max(f[i][i+n-1],ma);
memset(f,0x3f,sizeof f);
for(int i=1;i<=2*n;i++) f[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;
for(int k=i;k<j;k++) f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+a[j]-a[i-1]);
}
}
LL mi=1e9;
for(int i=1;i<=n;i++) mi=min(mi,f[i][i+n-1]);
cout<<mi<<endl<<ma;
}