CodeforcesRound#460(Div.2)D.SubstringBFS、拓扑排序、dp

5 4
abaca
1 2
1 3
3 4
4 5

3

6 6
xzyabc
1 2
3 1
2 3
5 4
4 3
6 4

-1

10 14
xzyzyzyzqx
1 2
2 4
3 5
4 5
2 6
6 8
6 5
2 10
3 9
10 9
4 6
1 10
2 8
3 7

4

Source

Codeforces Round #460 (Div. 2)

My Solution

题意：给出一个可能有环可能不连通的图，找出一个路径其上出现最多的字母出现的次数最大，求这个最大值。

BFS、拓扑排序、dp

这题与以前一个求最长路径的题差不多，这里定义状态dp[i][j]表示从某点开始跑到节点i时路径上出现字母j+'a'的最大次数。

只需要按照拓扑序跑一遍dp即可，

ch[v] != j, dp[v][j] = max(dp[v][j], dp[u][j]);

ch[v] != j, dp[v][j] = max(dp[v][j], dp[u][j] + 1);

最后如果度数不为0的点则有环，ans无穷大，置为-1.

否则 ans = max(ans, dp[i][j]).

时间复杂度 O(26*n)

空间复杂度 O(26*n)

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
typedef pair ii;
const int MAXN = 3e5 + 8;
const LL MOD = 142857;

string s;
LL ch[MAXN];
vector sons[MAXN];
int deg[MAXN];
LL dp[MAXN][26];
queue que;



inline void bfs()
{
    int fa, u, v, sz, i, j;
    while(!que.empty()){
        u = que.front().first;
        fa = que.front().second;
        que.pop();
        sz = sons[u].size();
        for(i = 0; i > n >> m;
    cin >> s;
    for(i = 1; i <= n; i++){
        ch[i] = s[i-1] - 'a';
    }
    for(i = 0; i > u >> v;
        sons[u].push_back(v);
    }
    for(i = 1; i <= n; i++){
        sz = sons[i].size();
        for(j = 0; j  
 
 
 
 
 
  Thank you!
 
 
                                                                                                                                             ------from ProLights