HDU6049

201707

• f(i,j)表示ai~aj最多能切成几块。如果区间不连续，f(i,j)=0。
  
  • 区间DP的思想。从小到大依次处理区间。la数组辅助计算。O(N^2)
• 枚举交换的第一个区间，第二个区间的右端点就确定了。维护答案即可。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define mp make_pair
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define de(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
//--------
const int N=3005;
int n;
int a[N],la[N],f[N][N],mi[N][N],ma[N][N];
int main() {
    int T;scanf("%d",&T);
    while(T--) {
        ///
        scanf("%d",&n);
        ///init
        memset(la,0,sizeof(la));    
        memset(f,0,sizeof(f));  
        ///read
        rep(i,1,n+1) scanf("%d",a+i);
        ///solve
        rep(i,1,n+1) {
            mi[i][i]=ma[i][i]=a[i];
            la[i]=i;
            f[i][i]=1;
            rep(j,i+1,n+1) {
                mi[i][j]=min(mi[i][j-1],a[j]);
                ma[i][j]=max(ma[i][j-1],a[j]);
            }
        }
        rep(len,2,n+1) {
            rep(i,1,n+1) {
                int j=len+i-1;
                if(j>n) break;
                if(ma[i][j]-mi[i][j]!=j-i) {
                    f[i][j]=0;
                } else {
                    if(mi[i][j]<mi[i][la[i]]) {
                        f[i][j]=1;
                    } else {
                        f[i][j]=f[i][la[i]]+f[la[i]+1][j];
                    }
                    la[i]=j;
                }
            }
        }
        int ans=f[1][n];
        rep(l1,1,n+1) {
            rep(r1,l1,n+1) {
                if(f[l1][r1]&&(l1==1||(f[1][l1-1]&&mi[1][l1-1]==1))) {
                    int r2=ma[l1][r1];
                    if(r2==n||(f[r2+1][n]&&ma[r2+1][n]==n)) {
                        for(int l2=r2;l2>r1;--l2) {
                            if(f[l2][r2]&&mi[l2][r2]==l1) {
                                ans=max(ans,f[1][l1-1]+f[r1+1][l2-1]+f[r2+1][n]+2);
                            }
                        }
                    }
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}