参考：http://www.cnblogs.com/FxxL/p/7253028.html
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> using namespace std; const int M=3044; int n; int s[M]; int f[M][M],mn[M][M],mx[M][M];//f是区间[i,j]可分成的最大的区间数，mn是区间[i,j]的最小值，mx是区间[i,j]的最大值 int sav[M],ans; void init()//预处理 { memset(f,0,sizeof(f)); int i,j,k; for(i=1;i<=n;i++) { sav[i]=i; f[i][i]=1; mn[i][i]=mx[i][i]=s[i]; } for(i=1;i<=n;i++) for(j=i+1;j<=n;j++) { mx[i][j]=max(mx[i][j-1],s[j]); mn[i][j]=min(mn[i][j-1],s[j]); } for(i=2;i<=n;i++) for(j=1;j+i-1<=n;j++) { k=j+i-1; if(mx[j][k]-mn[j][k]+1!=k-j+1) f[j][k]=0;//如果最大与最小的差！=区间内数的个数，即此区间非法； else { if(mn[j][k]<mn[j][sav[j]])//新来的比原来的小，就说明这段区间最多分1段 ； f[j][k]=1; else f[j][k]=f[j][sav[j]]+f[sav[j]+1][k]; sav[j]=k;//记录上一次的右端点； } } } int main() { int T,i,j; cin>>T; while(T--) { scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&s[i]); init(); ans=max(1,f[1][n]); int i,j,k,t,tmp; for(i=1;i<=n;i++) { for(j=i;j<=n;j++) { if(f[i][j] && (i==1 || (f[1][i-1] && mn[1][i-1]==1))) {//如果第一个区间不包含1，则交换的左区间就必须是此区间 //如果包含1，此区间右边第一个区间作为交换的左区间； k=mx[i][j]; if(k==n || (f[k+1][n] && mx[k+1][n]==n)) //右区间同理； { for(t=j+1;t<=k;t++) { if(mn[t][k]==i && f[t][k]) ans=max(ans,f[1][i-1]+1+f[j+1][t-1]+1+f[k+1][n]);//两个1分别代表f[i][j],f[t][k]; } } } } } cout<<ans<<endl; } return 0; }