CF-919D Substring 题解

题目大意

给你一个n个点，m条边的有向图，给你一个字符串，分别代表每一个点的值，定义一个路的大小为这个路上出现的最多的字母个数，问这个图的最大值是否可以无限大，可以则输出-1，否则求这个图中所有路中的最大值。

解题思路

这个题目还是有点难度的。

其实一开始是想到了需要用拓扑排序来判环，但是不知道如何求出最大路。

刚开始写的时候是理解成了最长路，后来发现不一定是最长的。

想了半天，都没想到dp的状态是咋写。

还是dp的题目写的不够多啊。

后面还是学长指点了我一下，就大致懂了。

可以用$dp[i][j]$来表示第i个点，字母j的最多的数量。

这样，在拓扑排序的过程中不断更新，最后枚举出最大值即可。

这个题目的解法还是很妙啊。

需要注意，只有起点需要初始化。

完整代码

#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;

const int N = 3e5 + 5;
vector<int>Map[N];
queue<int> q;
int in[N];
int dp[N][200];

int main() {
	int n, m;
	cin >> n >> m;
	string s;
	cin >> s;
	for (int i = 1; i <= m; i++) {
		int a, b;
		cin >> a >> b;
		Map[a].push_back(b);
		in[b]++;
	}
	for (int i = 1; i <= n; i++) {
		if (!in[i]) {
			q.push(i);
			dp[i][s[i-1]]++;
		}
	}
	int c = 0;
	while (!q.empty()) {
		int t = q.front();
		q.pop();
		c++;
		for (auto x : Map[t]) {
			in[x]--;
			for (int i = 'a'; i <= 'z'; i++)
				dp[x][i] = max(dp[x][i], dp[t][i]+(int)(s[x-1]==i));
			if (!in[x])	q.push(x);
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 'a'; j <= 'z'; j++)
			ans = max(ans, dp[i][j]);
	}
	if (c == n)	cout << ans << endl;
	else cout << -1 << endl;
}