盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码

ZOJ 3816 Generalized Palindromic Number(dp)

题目

源地址:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3816

题意

规定广义回文为:将字符串中相同的字符压缩为一个之后为回文串。例如:11233221->12321
现在给定一个n,求小于n的最大一个数,使其为广义回文串。(1≤n≤1e18)

思路

从最后一位(最右位)开始改动,一直改动到第一位(第一位最小到1,不能到0)。如果改动某一位可以得到一个回文串,答案就是这个数字。
现在假设改动到第k位:另dp[l][r]表示从第l位到第r位的符合回文的最大串
dp[l][r] = max(前缀和 base[r - L + 1] + dp[L][j] base[r - j] + 后缀和)
上述公式中:L为从l+1开始第一个与l不同的位,因为11121…的下一个状态直接转到21…(相同的1可以压缩)
j从r-1一直到k, 即把(j+1, r)的位全部变为l位

需要注意当r<=k时,此时dp[l][r]是已经确定的,我一开始直接判断该串是否为回文,但是这样不对。需要把右边和l-1相同的位全部压缩之后再判断。
例如:3443,当k为3,第三位为3时,dp[2][3] = 43,即3433,此时3433是广义回文,但43不是。所以应该判断4是不是为回文。

代码

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#include<map>
#include<set>
#define pb push_back
#define debug puts("=====================");
using namespace std;
typedef long long ll;
ll n;
int bit[22], len;
ll dp[22][22];
void work(ll n) {
vector<int> g;
len = 0;
while(n) {
g.pb(n % 10);
n /= 10;
}
len = g.size();
reverse(g.begin(), g.end());
for (int i = 1; i <= len; i++) bit[i] = g[i - 1];
}
int k;
ll base[22];
bool check(vector<int> g) {
int len = g.size();
for (int i = 0, j = len - 1; i < j; i++, j--) if (g[i] != g[j]) return false;
return true;
}
ll dfs(int l, int r) {
if (dp[l][r] != -1) return dp[l][r];
if (l > k) { //l>k,此时(l,r)为9...9最大
dp[l][r] = base[r - l + 1] - 1;
return dp[l][r];
}
if (r <= k) { //r <= k,此时(l,r)串为已知串
vector<int> g;
ll ss = 0;
ss = ss * 10 + bit[l];
g.pb(bit[l]);
for (int i = l + 1; i <= r; i++) {
ss = ss * 10 + bit[i];
}
int R = r;
while(bit[R] == bit[l - 1] && l > 1) R--; //需要把右边的压缩
for (int i = l + 1; i <= R; i++) {
if (bit[i] != bit[i - 1]) g.pb(bit[i]);
}
if (check(g)) return dp[l][r] = ss; //如果压缩后为回文串,修改值
return -1;
}
int L;
for (L = l + 1; L <= k; L++) { //把L变为第一个不与l位相同的
if (bit[L] != bit[L - 1]) break;
}
if (L == k + 1) ;
else if (L == k) {
if (bit[L] == bit[L - 1]) L = k + 1;
else L = k;
}
ll mx = -1;
ll ans = 0;
for (int i = l; i < L; i++) ans = ans * 10 + bit[i]; //前缀和
ll tmp = 0;
for (int j = r - 1; j >= k; j--) {
tmp = tmp * 10 + bit[l]; //后缀和
ll res = dfs(L, j);
if (res != -1) mx = max(ans * base[r - L + 1] + res * base[r - j] + tmp, mx);
}
if (mx >= 0) dp[l][r] = mx;
return mx;
}
int main () {
int t;
scanf("%d", &t);
base[0] = 1;
for (int i = 1; i <= 18; i++) base[i] = base[i - 1] * 10;
while(t--) {
scanf("%lld", &n);
work(n);
bool flag = false;
for (int i = len; i >= 1; i--) {
int x = bit[i];
for (int j = x - 1; j >= (i == 1) ? 1 : 0; j--) {
k = i;
memset(dp, -1, sizeof(dp));
bit[i] = j;
dfs(1, len);
if (dp[1][len] != -1) {
printf("%lld\n", dp[1][len]);
flag = true;
break;
}
}
bit[i] = x;
if (flag) break;
}
if (!flag) { //像100之类的数,上面的dp跑不出来,这里特别输出即可
printf("%lld\n", base[len - 1] - 1);
}
}
return 0;
}