Codeforces 919D(拓扑排序+DP)

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

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

Codeforces Submission

#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;
}