洛谷 P3607 题解

admin 2021-10-04 PM 40℃ 0条

题目链接

分析

很神奇的 DP 题。

这道题比较难的地方在于处理序列反转。

有一个关键的想法:序列反转不好记录,但是可以看做很多次交换数的位置。

也就是说,翻转子序列 $a_{i_1},a_{i_2},\ldots a_{i_k}$ 等价于交换 $a_{i_1}$ 和 $a_{i_k}$,$a_{i_2}$ 和 $a_{i_{k-1}}$ 等等。不需要考虑多了一个的情况,因为这个数根本就不会改变位置,把它从 $i$ 中去掉就好。很可能是一个区间 DP。

需要快速判断一个数能否作贡献,而且值域也只有 50,状态里面可以考虑带值域。

所以,基本上可以设出状态:设 $dp_{l,r,L,R}$ 为原序列中 $l$ 到 $r$ 的区间里,所有值为 $L$ 到 $R$ 的数经过翻转后可以组成的最长 LIS 长度。

考虑如何转移。

首先,$a_l$ 和 $a_r$ 可能不在 $[L,R]$ 中,所以要通过 $dp_{l,r,L+1,R}$ 和 $dp_{l,r,L,R-1}$ 转移。

其次考虑交换 $a_l$ 和 $a_r$ 位置的情况下,$a_l$ 作的贡献。不被包括在第一种情况的只有 $a_l=L$ 且算入 LIS 的情况。从 $dp_{l+1,r,L,R}+[a_l=L]$ 转移。同理要从 $dp_{l,r-1,L,R}+[a_r=R]$ 转移。

最后考虑交换 $a_l$ 和 $a_r$ 的情况。不被包括在第一种情况的只有 $a_l=R$ 或者 $a_r=L$ 的情况。从 $dp_{l+1,r-1,L,R}+[a_l=R]+[a_r=L]$ 转移。

答案是 $dp_{1,n,1,50}$。

解决

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 55;
int n, a[N], dp[N][N][N][N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        for (int L = 1; L <= a[i]; L++)
            for (int R = a[i]; R <= 50; R++)
                dp[i][i][L][R] = 1;
    }
    for (int l1 = 2; l1 <= n; l1++)
        for (int l = 1, r = l1; r <= n; l++, r++)
            for (int l2 = 1; l2 <= 50; l2++)
                for (int L = 1, R = l2; R <= 50; L++, R++)
                {
                    dp[l][r][L][R] = max(dp[l][r][L + 1][R], dp[l][r][L][R - 1]);
                    dp[l][r][L][R] = max(dp[l][r][L][R], dp[l + 1][r][L][R] + (a[l] == L));
                    dp[l][r][L][R] = max(dp[l][r][L][R], dp[l][r - 1][L][R] + (a[r] == R));
                    dp[l][r][L][R] = max(dp[l][r][L][R], dp[l + 1][r - 1][L][R] + (a[l] == R) + (a[r] == L));
                }
    cout << dp[1][n][1][50] << endl;
    return 0;
}
标签: 妙妙题, 动态规划

非特殊说明,本博所有文章均为博主原创。

上一篇 洛谷 P5591 题解
下一篇 CF 631E 题解

评论啦~