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;
}