四边形不等式
陈子骏
2018-07-11 21:01:40
```
#include<bits/stdc++.h>
using namespace std;
int s[2001][2001],sum[2001],a[2001],f1[2001][2001],f2[2001][2001];
int main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
a[i+n]=a[i];
sum[i]=sum[i-1]+a[i];
s[i][i]=i;
}
for(int i=1+n;i<=(n<<1);i++){
sum[i]=sum[i-1]+a[i];
s[i][i]=i;
}
for(int i=2*n-1;i;i--)
for(int j=i+1;j<=2*n;j++)
{
int temp=0x3f3f3f3f,jc=0;
f2[i][j]=max(f2[i][j-1],f2[i+1][j])+sum[j]-sum[i-1];
for(int k=s[i][j-1];k<=s[i+1][j];k++)
{
int t=f1[i][k]+f1[k+1][j]+sum[j]-sum[i-1];
if(temp>t)temp=t,jc=k;
}
s[i][j]=jc,f1[i][j]=temp;
}
int ans2=0x3f3f3f3f,ans1=0;
for(int i=1;i<=n;i++)
{
ans1=max(ans1,f2[i][i+n-1]);
ans2=min(ans2,f1[i][i+n-1]);
}
printf("%d\n%d\n",ans2,ans1);
}
```