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