神思路orzorzorzorzorzorz
首先可以这么想：对一个子序列翻转即是相当于对i1<i2<....<ik<jk<jk-1<....j1，swap(i,j)。
然后dp[i][j][k][m]表示对于区间i,j，它前面的最大值是k，它后面的最小值是m，的答案。
转移分成两类：一类是swap(i,j)，另一类是不swap。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 55 using namespace std; int n,a[maxn],dp[maxn][maxn][maxn][maxn]; int get_dp(int i,int j,int k,int m) { if (dp[i][j][k][m]!=-1) return dp[i][j][k][m]; if (k>m) return -(1<<29); if (i>j) return 0; if (i==j) return a[i]<=m && a[i]>=k; int ret=0; ret=max(ret,get_dp(i+1,j-1,k,m)); if (a[j]>=k) ret=max(ret,get_dp(i+1,j-1,a[j],m)+1); if (a[i]<=m) ret=max(ret,get_dp(i+1,j-1,k,a[i])+1); if (k<=a[j] && a[j]<=a[i] && a[i]<=m) ret=max(ret,get_dp(i+1,j-1,a[j],a[i])+2); ret=max(ret,get_dp(i+1,j,k,m)); if (a[i]>=k) ret=max(ret,get_dp(i+1,j,a[i],m)+1); ret=max(ret,get_dp(i,j-1,k,m)); if (a[j]<=m) ret=max(ret,get_dp(i,j-1,k,a[j])+1); if (k<=a[i] && a[i]<=a[j] && a[j]<=m) ret=max(ret,get_dp(i+1,j-1,a[i],a[j])+2); return dp[i][j][k][m]=ret; } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]); memset(dp,-1,sizeof(dp)); printf("%d ",get_dp(1,n,0,50)); return 0; }