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
| #include <bits/stdc++.h> #define ll long long
using namespace std;
const int N = 2005; const int INF = (int)1e9;
int n; ll k; char s[N]; int f[N][N]; ll g[N][N];
string solve(int l, int r, ll k) { if(l > r) return ""; if(l == r) { string t = ""; t += s[l]; return t; } if(s[l] == s[r]) return s[l] + solve(l + 1, r - 1, k) + s[r]; if(f[l + 1][r] < f[l][r - 1]) return s[l] + solve(l + 1, r, k) + s[l]; if(f[l + 1][r] > f[l][r - 1]) return s[r] + solve(l, r - 1, k) + s[r]; if(s[l] < s[r]) { if(g[l + 1][r] >= k) return s[l] + solve(l + 1, r, k) + s[l]; else return s[r] + solve(l, r - 1, k - g[l + 1][r]) + s[r]; } else { if(g[l][r - 1] >= k) return s[r] + solve(l, r - 1, k) + s[r]; else return s[l] + solve(l + 1, r, k - g[l][r - 1]) + s[l]; } }
int main() { scanf("%s %lld", s + 1, &k); n = strlen(s + 1); for(int i = 1; i <= n; i++) f[i][i] = 0, g[i][i] = 1; for(int l = 2; l <= n; l++) { for(int i = 1; i <= n - l + 1; i++) { if(l == 2) { if(s[i] == s[i + 1]) { f[i][i + 1] = 0, g[i][i + 1] = 1; } else { f[i][i + 1] = 1; g[i][i + 1] = 2; } continue ; } int L = i, R = (i + l - 1); int mn = INF; if(s[L] == s[R]) { f[L][R] = f[L + 1][R - 1]; g[L][R] = g[L + 1][R - 1]; continue ; } mn = min(mn, 1 + min(f[L][R - 1], f[L + 1][R])); f[L][R] = mn; if(mn == f[L + 1][R] + 1) { g[L][R] += g[L + 1][R]; } if(mn == f[L][R - 1] + 1) { g[L][R] += g[L][R - 1]; } if(g[L][R] > k) g[L][R] = k + 1; } } if(k > g[1][n]) { puts("NONE"); return 0; } cout << solve(1, n, k) << endl; return 0; }
|