题目大意

传说中，有一个字符王国，王国里有n个城市，每个城市都将一个字符作为自己城市的象征。城市和城市之间有边相连，整个王国共有m条边（有向）。（2 <= n,m <= 300000）

我们定义一条路径的枯燥度为这条路径上出现次数最多的字符出现的次数。

现在字符王国的国王想知道，王国里最枯燥的路径的枯燥度有多大。

输入

第一行两个整数n,m表示城市数量和边数
第二行一个长为n的字符串，其中第i个字符表示编号为i的城市的代表字符
接下来m行，每行两个整数x,y，表示城市x和城市y之间有一条边

输出

一行一个整数表示王国里最枯燥的路径的枯燥度

数据范围

10% 2 <= n, m <= 15
30% 2 <= n ,m <= 1000
100% 2 <= n,m <= 300000

输入样例

输出样例

这个题说了是一个有向图，然后看了眼tag是dp，那就往dp上想，这里每个点的字符只有26种，

就尝试一下dp[i][j]表示一个是i个点，一个是第j个字符（1-26）

然后考虑这个数组的具体含义

因为我从u点转移到d点的时候，发生数量变化的字母只有v这个点上的字母

而其他字母都可以沿用过去

所以得到方程

f[v][j] = max(f[v][j],f[u][j]+(val[v]==j))

具体操作：

我们起点肯定是入度为0的点，终点肯定是出度为0的点

在拓扑序上dp完后扫一遍出度为0的点的26个字母就行了，取个max

CODE：

vector<int>e[maxn];
int n,m,val[maxn],in[maxn];
int f[maxn][28],cnt,ans;
void solve() {
    queue<int>q;
    rep(i,1,n) if(in[i]==0) q.push(i),f[i][val[i]] = 1;

    while(q.size()) {
        int u = q.front();
        q.pop();
        for(int v:e[u]) {
            for(int j=1 ; j<=26 ; j++) {
                f[v][j] = max(f[v][j],f[u][j]+(val[v]==j));
            }
            in[v]--;
            if(in[v]==0) q.push(v);
        }
    }

    for(int i=1 ; i<=n ; i++) {
        if(e[i].size()) continue;
        for(int j=1 ; j<=26; j++) {
            ans = max(ans,f[i][j]);
        }
    }
    out(ans);
}
int main() {
    n=read(),m=read();
    for(int i=1 ; i<=n ; i++) {
        char c;
        cin>>c;
        val[i] = c-'a'+1;
    }
    for(int i=1 ; i<=m ; i++) {
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        in[v]++;
    }
    solve();
    return  0;
}

View Code

51nod-3118-字符王国（DAG上dp）