题目描述
在一个园形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.
题解
我们目测一个dp方程
设f[i][j]表示i到j合并的最小（大）价值
那么
dp的时候按照区间长度递增来dp
首先最大值，根据单调性 肯定是从
和
转移来的
最小值的时候。这个东西满足四边形不等式
设表示使i~j最优的分界点
首先当时
满足
且
那么枚举中间点的时候只要从枚举到
复杂度证明。。
这样一坨可以两两抓出来消掉
就是这个<=n。复杂度就可证为
这是最小值的做法
#include<map>
#include<stack>
#include<queue>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<complex>
#include<iostream>
#include<assert.h>
#include<algorithm>
using namespace std;
#define inf 1001001001
#define infll 1001001001001001001LL
#define ll long long
#define dbg(vari) cerr<<#vari<<" = "<<(vari)<<endl
#define gmax(a,b) (a)=max((a),(b))
#define gmin(a,b) (a)=min((a),(b))
#define Ri register int
#define gc getchar()
#define il inline
il int read(){
bool f=true;Ri x=0;char ch;while(!isdigit(ch=gc))if(ch=='-')f=false;while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=gc;}return f?x:-x;
}
#define gi read()
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout); using namespace std;
int n;
int a[2333],s[2333],f[2333][2333],g[2333][2333];
int main(){
n=gi;
for(int i=1;i<=n;i++) a[i]=a[i+n]=gi;
for(int i=1;i<=n+n;i++) s[i]=s[i-1]+a[i];
for(int i=1;i<=n+n;i++) f[i][i]=0,g[i][i]=i;
for(int l=1;l<n;l++)
for(int i=1;i<=2*n-l;i++){
int j=l+i;
f[i][j]=inf/2;
for (int k=g[i][j-1];k<=g[i+1][j];k++)
if (f[i][k-1]+f[k][j]<f[i][j]){
f[i][j]=f[i][k-1]+f[k][j];
g[i][j]=k;
}
f[i][j]+=s[j]-s[i-1];
} int ans=inf;
for(int i=1;i<=n;i++) ans=min(ans,f[i][i+n-1]);
printf("%d\n",ans);
for (int i=1;i<=2*n;i++) f[i][i]=0;
for (int k=1;k<=n-1;k++)
for (int i=1;i<=2*n-k;i++){
int j=i+k;
if (f[i][j-1]>f[i+1][j])
f[i][j]=f[i][j-1]+s[j]-s[i-1];
else
f[i][j]=f[i+1][j]+s[j]-s[i-1];
}
ans=0;
for (int i=1;i<=n;i++) ans=max(ans,f[i][i+n-1]);
printf("%d\n",ans);
return 0;
}