题意：

[0,x]中全是1，判断[1,n]中的点i中是0还是1需要权值 ai a i ，最坏情况下求得到x的最小权值

n<=2000 n <= 2000

Solution:

f[i][j] f [ i ] [ j ] 表示只考虑[i,j]，最坏情况下求得到x的最小权值

那么 f[i][j]=minjk=i(max(f[i][k−1],f[k+1][j])+a[k]) f [ i ] [ j ] = m i n k = i j ( m a x ( f [ i ] [ k − 1 ] , f [ k + 1 ] [ j ] ) + a [ k ] )

这样就得到了一个 O(n3) O ( n 3 ) 的做法

考虑优化：

发现在左端点或右端点固定的时候，f的值随着区间的长度增大而增大，说明最大值是 f[i][k−1] f [ i ] [ k − 1 ] 或 f[k+1][j] f [ k + 1 ] [ j ] 时，分别对应的是一段区间，那么我们可以二分分割点g，用一堆线段树维护 f[i][k−1]+a[k],g⩽k⩽j f [ i ] [ k − 1 ] + a [ k ] , g ⩽ k ⩽ j 和 f[k+1][j]+a[k],i⩽k<g f [ k + 1 ] [ j ] + a [ k ] , i ⩽ k < g 即可

时间复杂度 O(n2logn) O ( n 2 l o g n ) 因为要建2n棵线段树，所以空间复杂度极高，需要使用zkw线段树优化，勉强可过此题

那么还能不能继续优化呢？

我们还可以发现一个性质：对于每个状态 f[i][j] f [ i ] [ j ] ，它的分割点 g[i][j] g [ i ] [ j ] 满足这样一个性质： g[i][j]≤g[i][j+1],g[i][j]≤g[i+1][j] g [ i ] [ j ] ≤ g [ i ] [ j + 1 ] , g [ i ] [ j ] ≤ g [ i + 1 ] [ j ]

所以我们可以使用单调队列来优化转移：

我们建立n+1个单调队列，1个来维护i固定时，随着j增长所能得到的最小值

剩下的n个维护j固定时，随着i递减所能得到的最小值

这样复杂度变为 O(n2) O ( n 2 )

代码：

#include<cstdio>
#include<iostream>
using namespace std;
const int N=2010;
int n,a[N],q[N][N],h[N],t[N],f[N][N],g;
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);   
    for (int i=n;i>=1;i--)
    {
        f[i][i]=a[i],g=i;
        h[0]=1;t[0]=0;
        h[i]=t[i]=1;q[i][1]=i;
        for (int j=i+1;j<=n;j++)
        {
            while (g<j&&f[i][g-1]<f[g+1][j]) g++;
            while (h[0]<=t[0]&&q[0][h[0]]<g) h[0]++;
            while (h[0]<=t[0]&&f[i][q[0][t[0]]-1]+a[q[0][t[0]]]>f[i][j-1]+a[j]) t[0]--;
            q[0][++t[0]]=j;

            while (h[j]<=t[j]&&q[j][h[j]]>=g) h[j]++;
            while (h[j]<=t[j]&&f[q[j][t[j]]+1][j]+a[q[j][t[j]]]>f[i+1][j]+a[i]) t[j]--;
            q[j][++t[j]]=i;

            f[i][j]=min(f[i][q[0][h[0]]-1]+a[q[0][h[0]]],f[q[j][h[j]]+1][j]+a[q[j][h[j]]]);
        }
    }
    printf("%d",f[1][n]);
}