P3607 [USACO17JAN] Subsequence Reversal P 题解

P3607 [USACO17JAN] Subsequence Reversal P 题解

如果我们顺序对翻转的子序列做 DP，那么在末尾新增一个数会影响前面所有数的交换对应关系。

思考这个翻转的结构，前后对应的数交换，如果我们同时加入前后两个对应的数，就不会影响中间所有数的交换关系。

所以我们考虑区间 DP，\(f_{i, j, x, y}\) 表示只考虑区间 \([i, j]\)，其中 LIS 的开头/结尾位置分别是 \(x, y\) 的 LIS 长度。

第一种转移是保留原来的 LIS 不动，直接转移到 \(f_{i - 1,j , x, y}\) 和 \(f_{i, j + 1, x, y}\)。

第二种转移是选择 \(i - 1\) 或 \(j + 1\) 作为新 LIS 的一部分，转移到 \(f_{i - 1, j, i - 1, y}\) 和 \(f_{i, j + 1, x, j + 1}\)。

第三种转移是翻转 \((i - 1, j + 1)\)，转移到 \(f_{i - 1, j + 1, j + 1, i - 1}\) 等。

时间复杂度 \(O(n^4)\)。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <ctime>
//#define int long long
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
typedef long double ld;
const int N = 55;int n, f[N][N][N][N], a[N];signed main() {ios::sync_with_stdio(0), cin.tie(0);cin >> n;for(int i = 1; i <= n; i ++) cin >> a[i];memset(f, -0x3f, sizeof f);for(int i = 1; i <= n; i ++) {f[i][i][i][i] = 1;if(i < n && a[i + 1] <= a[i]) f[i][i + 1][i + 1][i] = 2;}for(int len = 1; len < n; len ++) {for(int i = 1; i + len - 1 <= n; i ++) {int j = i + len - 1;for(int k = i; k <= j; k ++) {for(int p = i; p <= j; p ++) {int t = f[i][j][k][p];f[i - 1][j][k][p] = max(f[i - 1][j][k][p], t);f[i][j + 1][k][p] = max(f[i][j + 1][k][p], t);if(i > 1 && a[i - 1] <= a[k]) f[i - 1][j][i - 1][p] = max(f[i - 1][j][i - 1][p], t + 1);if(j < n && a[j + 1] >= a[p]) f[i][j + 1][k][j + 1] = max(f[i][j + 1][k][j + 1], t + 1);if(i > 1 && j < n) {if(a[i - 1] >= a[p]) f[i - 1][j + 1][k][i - 1] = max(f[i - 1][j + 1][k][i - 1], t + 1);if(a[j + 1] <= a[k]) f[i - 1][j + 1][j + 1][p] = max(f[i - 1][j + 1][j + 1][p], t + 1);if(a[j + 1] <= a[k] && a[i - 1] >= a[p]) f[i - 1][j + 1][j + 1][i - 1] = max(f[i - 1][j + 1][j + 1][i - 1], t + 2);}}}}}int ans = 0;for(int k = 1; k <= n; k ++) for(int p = 1; p <= n; p ++) ans = max(ans, f[1][n][k][p]);cout << ans << '\n';return 0;
}