https://codeforces.com/gym/102114
H. Hills And Valleys
题意：给定一个长为 1≤n≤105 的数组 A，0≤Ai≤9，要求翻转一个区间，使得新数组的最长不下降子序列最长。输出长度与翻转的区间。
dp
先假设不翻转。
设有数组 B[10]={0,1,2,3,4,5,6,7,8,9}，则数组 A 的最长不下降子序列可以视为与 B 的特殊的最长公共子序列，特殊之处在于 A 的子序列中连续的相同数字可以视为一个数字。
转移方程也与普通最长公共子序列类似：原来是 dp[i][j]=dp[i−1][j−1]+1，现在是 dp[i][j]=dp[i−1][j]+1。
现在要翻转 A 数组，变成翻转 B 数组，因为 B 很短，所以直接枚举翻转区间。再求出这个特殊的最长公共子序列，同时要记录下dp路径，看与当前翻转区间对应的是 A 数组中哪一个区间。
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
| #include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
const double eps = 1e-8;
const double PI = acos(-1);
typedef pair<int, int> pii;
int T, n;
char s[N];
int a[N], b[30];
int v[N], l[N], r[N], c[N];
int dp[N][30];
pii f[N][30];
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
scanf("%s", s + 1);
for (int i = 1; i <= n; i++) {
a[i] = s[i] - '0';
}
int m = 1;
l[1] = 1;
v[1] = a[1];
for (int i = 2; i <= n; i++) {
if (a[i] != a[i - 1]) {
v[++m] = a[i];
l[m] = i;
r[m - 1] = i - 1;
c[m - 1] = i - l[m - 1];
}
}
r[m] = n;
c[m] = n - l[m] + 1;
for (int i = 1; i <= 20; i++)b[i] = (i - 1) / 2;
int ans = 0, L = 0, R = 0;
for (int i = 1; i <= 20; i++) {
for (int j = i; j <= 20; j++) {
dp[0][0] = dp[0][1] = dp[1][0] = 0;
reverse(b + i, b + j + 1);
for (int k = 1; k <= m; k++) {
for (int p = 1; p <= 20; p++) {
dp[k][p] = dp[k - 1][p];
f[k][p] = f[k - 1][p];
if (dp[k][p - 1] > dp[k][p]) {
dp[k][p] = dp[k][p - 1];
f[k][p] = f[k][p - 1];
}
if (v[k] == b[p] && dp[k - 1][p] + c[k] > dp[k][p]) {
dp[k][p] = max(dp[k][p], dp[k - 1][p] + c[k]);
f[k][p] = {k, p};
}
}
}
if (dp[m][20] > ans) {
int tl=0,tr=0;
pii u = {m, 20};
while (u.first > 0 && u.second > 0) {
u = f[u.first][u.second];
if (u.second == i)tl = l[u.first];
if (u.second == j)tr = max(tr, r[u.first]);
u.first--;
}
if(tl && tr){
ans = dp[m][20];
L = tl;
R = tr;
}
}
reverse(b + i, b + j + 1);
}
}
printf("%d %d %d\n", ans, L, R);
}
return 0;
}
|
