P3607 [USACO17JAN] Subsequence Reversal P

Description

https://www.luogu.com.cn/problem/P3607

Solution

只记录区间是难处理的，考虑多记录值域 $[l,r]$ ，表示在区间的 $[i,j]$ 值域 $[l,r]$ 之间的最长不下降子序列。

转移简单。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#define maxn 55
int n,a[maxn],f[maxn][maxn][maxn][maxn];
inline void amax(int &x,int y) {x=max(x,y);}
const int base=50;
signed main(void){
	int i,j,l,r;
	read(n);
	for (i=1;i<=n;i++) read(a[i]),f[i][i][a[i]][a[i]]=1;
	for (i=1;i<n;i++) f[i][i+1][min(a[i],a[i+1])][max(a[i],a[i+1])]=2;
	for (i=n;i>=1;i--) {
		for (j=i;j<=n;j++) {
			for (l=base;l>=1;l--)
				for (r=l+1;r<=base;r++) {
					amax(f[i][j][l][r],max(f[i][j][l+1][r],f[i][j][l][r-1]));
					amax(f[i][j][l][r],f[i+1][j][l][r]+(a[i]==l));
					amax(f[i][j][l][r],f[i][j-1][l][r]+(a[j]==r));
					amax(f[i][j][l][r],f[i+1][j-1][l][r]+(a[i]==r)+(a[j]==l));
				}
		}
	}
	printf("%d",f[1][n][1][base]);
	return 0;
}