明天考试。
今天写什么 jb 石子合并 3，然后发现要优化，于是看了眼题解里写的都是四边形不等式。
朴素 N^3算法
void work(int a[],int n)
{
for(int i=0;i<n;++i)
dpmin[i][0]=dpmax[i][0]=0;
for(int j=1;j<n;++j)
for(int i=0;i<n;++i)
{
dpmin[i][j]=INF;
dpmax[i][j]=0;
for(int k=0;k<j;++k)
{
dpmin[i][j]=min(dpmin[i][j],dpmin[i][k]+dpmin[(i+k+1)%n][j-k-1]+get(i,j));
dpmax[i][j]=max(dpmax[i][j],dpmax[i][k]+dpmax[(i+k+1)%n][j-k-1]+get(i,j));
}
}
minal=dpmin[0][n-1];
maxal=dpmax[0][n-1];
for(int i=0;i<n;++i)
{
minal=min(minal,dpmin[i][n-1]);
maxal=max(maxal,dpmax[i][n-1]);
}
}
优化后的式子 N^2
for (int r=1;r<n;r++)
for (int i=1;i<n;i++)
{
int j=i+r;
if(j>n) break;
dp[i][j]=0;
for (int k=s[i][j-1];k>=s[i+1][j];k++)
if(dp[i][j]>dp[i][k]+dp[k+1][j])
{
dp[i][j]=dp[i][k]+dp[k+1][j];
s[i][j]=k;
}
dp[i][j]+=sum[j]-sum[i-1];
}
但是四边形不等式只能求解求最小值的环形石子合并问题，OJ上是求最大值。
不能求最大值。（为啥）
但是求最大值有一个性质，总是在两个端点的最大者中取到。
于是可以优化成N^2
for(int i=2;i<=n;++i)
for(int j=1,k;(k=i+j-1)<=2*n;++j)
dp[j][k]=max(dp[j][k-1],dp[j+1][k])+sum[k]-sum[j-1];
可以通过 \(n<=2000\) 的数据。
插曲：我电脑上有个Veyon监视，然后我杀了他几次后发现没了，我挺高兴，打了半天代码，然后把我的博客园一刷新，诶我草，我网呢？
原来是我网线松了。
插上去之后监视又回来了。
挺谔谔的
寄
标签：11.29,int,最大值,四边形,sum,dp From： https://www.cnblogs.com/iNFiNiTE-ENERZY-Overdose-/p/17865920.html