QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#410390#3169. Editing Explosionucup-team1716AC ✓224ms12868kbC++141.4kb2024-05-13 22:54:412024-05-13 22:54:41

Judging History

你现在查看的是最新测评结果

  • [2024-05-13 22:54:41]
  • 评测
  • 测评结果:AC
  • 用时:224ms
  • 内存:12868kb
  • [2024-05-13 22:54:41]
  • 提交

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'