Codeforces 919D(拓扑排序+区间DP)

Codeforces 919D
题意:给出一个有向图,每个点有一个小写英文字母,求一条路径使得路径上有一种字母数出现频率最多
这题如果不是图可以想到DP,设$dp(i,j)$为在$i$处,$j$字母时的最大值
放在图中,如果想DP,又不保证是DAG,那么就要用拓扑序来无后效性转移

ps: 图中要判环的一般是SPFA,拓扑排序,DFS

Codeforces Submission

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
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
#define ms(i, j) memset(i, j, sizeof i)
#define ll long long
int n, m, ino[300000 + 5], seq[300000 + 5], idx, dp[300000 + 5][30];
char s[300000 + 5];
vector<int> G[300000 + 5];
int topsort() {
queue<int> q;
for (int i = 1; i <= n; i++) if (ino[i] == 0) seq[++idx] = i, q.push(i);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = 0; i < (int)G[u].size(); i++) {
int v = G[u][i];
ino[v]--;
if (ino[v] == 0) seq[++idx] = v, q.push(v);
}
}
if (idx != n) return 0;
return 1;
}
void clean() {
idx = 0, ms(ino, 0), ms(dp, 0);
}
int solve() {
clean();
for (int i = 1; i <= m; i++) {
int x, y;
scanf("%d%d", &x, &y);
G[x].push_back(y), ino[y]++;
}
if (!topsort()) return printf("-1\n"), 0;
for (int i = 1; i <= n; i++) {
int u = seq[i];
dp[u][s[u] - 'a']++;
for (int j = 0; j < (int)G[u].size(); j++) {
int v = G[u][j];
for (int c = 0; c < 26; c++) {
dp[v][c] = max(dp[v][c], dp[u][c]);
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int c = 0; c < 26; c++) {
ans = max(ans, dp[i][c]);
}
}
printf("%d\n", ans);
return 0;
}
int main() {
scanf("%d%d%s", &n, &m, s + 1), solve();
return 0;
}

------ 本文结束 ------