QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#410390 | #3169. Editing Explosion | ucup-team1716 | AC ✓ | 224ms | 12868kb | C++14 | 1.4kb | 2024-05-13 22:54:41 | 2024-05-13 22:54:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int MOD = 998244353;
inline int mod1(int x) { return x < MOD ? x : x - MOD; }
inline int mod2(int x) { return x < 0 ? x + MOD : x; }
inline void add(int &x, int y) { x = mod1(x + y); }
inline void sub(int &x, int y) { x = mod2(x - y); }
int n, d;
string s;
map<vector<int>, int> f[21];
int main() {
cin >> s >> d;
n = s.length();
s = "@" + s; // 1-indexed
vector<int> v(n + 1);
for (int i = 0; i <= n; ++i) {
v[i] = i;
}
f[0][v] = 1;
for (int i = 1; i <= n + d; ++i) {
for (map<vector<int>, int> :: iterator it = f[i - 1].begin(); it != f[i - 1].end(); ++it) {
vector<int> olddp = (it -> fi);
for (int c = 'A'; c <= 'Z'; ++c) {
vector<int> newdp(n + 1);
newdp[0] = i;
for (int j = 1; j <= n; ++j) {
// dp[i][j] = min{ dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + (s[i] != t[j]) }
newdp[j] = min(min(olddp[j] + 1, newdp[j - 1] + 1), olddp[j - 1] + (s[j] != c));
if (newdp[j] > 11) {
newdp[j] = 11;
}
}
add(f[i][newdp], it -> se);
}
}
}
int ans = 0;
for (int l = 0; l <= n + d; ++l) {
for (map<vector<int>, int> :: iterator it = f[l].begin(); it != f[l].end(); ++it) {
vector<int> dp = (it -> fi);
if (dp[n] == d) {
add(ans, it -> se);
}
}
}
cout << ans << endl;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3644kb
input:
ICPC 1
output:
230
result:
ok single line: '230'
Test #2:
score: 0
Accepted
time: 127ms
memory: 9380kb
input:
PROGRAMMER 10
output:
110123966
result:
ok single line: '110123966'
Test #3:
score: 0
Accepted
time: 224ms
memory: 12868kb
input:
ABCDEFGHIJ 10
output:
258519532
result:
ok single line: '258519532'
Test #4:
score: 0
Accepted
time: 8ms
memory: 4240kb
input:
AAAAABBBBB 10
output:
877770338
result:
ok single line: '877770338'
Test #5:
score: 0
Accepted
time: 12ms
memory: 4584kb
input:
NOWISTHE 0
output:
1
result:
ok single line: '1'
Test #6:
score: 0
Accepted
time: 16ms
memory: 4796kb
input:
NOWISTHE 1
output:
434
result:
ok single line: '434'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3832kb
input:
ABABABABAB 10
output:
555168781
result:
ok single line: '555168781'
Test #8:
score: 0
Accepted
time: 191ms
memory: 11812kb
input:
ABCDDEFGHI 3
output:
21580956
result:
ok single line: '21580956'
Test #9:
score: 0
Accepted
time: 197ms
memory: 12120kb
input:
ABCDDEFGHI 8
output:
49338700
result:
ok single line: '49338700'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
A 10
output:
864056661
result:
ok single line: '864056661'