Subsequence Reversal P
思路：
发现，翻转一个子序列，就意味着两两互换子序列里面的东西。
于是我们就可以设 \(f[l][r][L][R]\) 表示： \(\max[1,l)=L,\min(r,n]=R\) 时的最长长度。
则边界为： \(L>R\) 时， \(f=-\infty\)；否则，如果 \(l>r,f=0\)。
然后开始转移。
1、不选。
\(f[l+1][r][L][R]\) 和 \(f[l][r-1][L][R]\)。
2、选一个。
\(\bullet\) 当 \(a_l\geq L\) 时，\(f[l+1][r][a_l][R]+1\)。
\(\bullet\) 当 \(a_r\leq R\) 时，\(f[l][r-1][L][a_r]+1\)。
3、翻转，必须有 \(l<r\)。
\(\bullet\) 当 \(a_r\geq L\) 时，\(f[l+1][r-1][a_r][R]+1\)。
\(\bullet\) 当 \(a_l\leq R\) 时，\(f[l+1][r-1][L][a_l]+1\)。
\(\bullet\) 当 \(a_r\geq L\) 且 \(a_l\leq R\) 时，\(f[l+1][r-1][a_r][a_l]+2\)。
最终答案为 \(f[1][n][0][\infty]\)，其中 \(\infty=50\) 足矣。
#include<bits/stdc++.h>
using namespace std;
const int INF=0x80808080;
const int N=60;
int n;
int f[N][N][N][N],a[N];
int solve(int l,int r,int L,int R){
if(L>R) return INF;
if(l>r) return 0;
if(f[l][r][L][R]!=-1) return f[l][r][L][R];
int &res=f[l][r][L][R];
res=0;
res=max(res,solve(l+1,r,L,R));
res=max(res,solve(l,r-1,L,R));
if(a[l]>=L) res=max(res,solve(l+1,r,a[l],R)+1);
if(a[r]>=L&&l!=r) res=max(res,solve(l+1,r-1,a[r],R)+1);
if(a[r]<=R) res=max(res,solve(l,r-1,L,a[r])+1);
if(a[l]<=R&&l!=r) res=max(res,solve(l+1,r-1,L,a[l])+1);
if(a[l]<=R&&a[r]>=L&&l!=r) res=max(res,solve(l+1,r-1,a[r],a[l])+2);
// printf("(%d,%d):(%d,%d):%d\n",l,r,L,R,res);
return res;
}
int main(){
scanf("%d",&n);
memset(f,-1,sizeof(f));
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
printf("%d\n",solve(1,n,0,50));
return 0;
}