BZOJ 4758.「USACO 2017 · January」Subsequence Reversal

奇妙的套路区间 DP。

注意到翻转一个子序列相当于从内到外一次交换某一对数,所以考虑设 \(f_{l,r,i,j}\) 表示区间 \([l,r]\) 的值域在 \([i,j]\) 的最长不下降子序列长度。
然后就很 SB 了。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 50;
int n,a[N + 5];
int f[N + 5][N + 5][N + 5][N + 5];
int dfs(int l,int r,int x,int y)
{
if(l > r || x > y)
return 0;
if(~f[l][r][x][y])
return f[l][r][x][y];
int ret = max(dfs(l,r,x + 1,y),dfs(l,r,x,y - 1));
ret = max(ret,dfs(l + 1,r,x,y) + (a[l] == x));
ret = max(ret,dfs(l,r - 1,x,y) + (a[r] == y));
ret = max(ret,dfs(l + 1,r - 1,x,y) + (a[l] == y) + (a[r] == x));
return f[l][r][x][y] = ret;
}
int main()
{
scanf("%d",&n),memset(f,-1,sizeof f);
for(register int i = 1;i <= n;++i)
scanf("%d",a + i),f[i][i][a[i]][a[i]] = 1;
printf("%d\n",dfs(1,n,1,N));
}