codeforces 919D Substring(简单dp)

题意:给定n个结点，每个结点都有一个小写字符，再给定m条边，寻找一条路径使得这条路径上所有的结点组合起来的字符串中相同字符数最多。 例如 abaac ，其中a有3个即最多。 若这个图有环则输出-1。(注意，图不一定是连通的)

做法: 对图进行拓扑排序的过程中进行状态转移。
d [i][k] 代表第i个结点中k字符的数目。
状态转移: d[j][k] = max( d[i][k] + ( node[j] == k) ) // k ∈ [0,26]
// j 是与 i相邻的点。
node[j] == k 判断与 i 相邻的结点j 的字符是否和k一样。
初始每个结点其自身字符个数都为1。

判断是否成环: 若拓扑结束发现 排序的结点小于n则说明有环。

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <vector>
#include <cmath>
using namespace std;
#define fre freopen("/Users/user/Desktop/in.txt","r",stdin);
#define CLR(s) memset(s,0,sizeof(s));
#define all(x) x.begin(), x.end()
const int maxn = 300000+10;
vector <int> G[maxn]; // 领接表存储图。
char node[maxn];
int N,M;
int ind[maxn];
int d[maxn][27];
void add(int from,int to){
G[from].push_back(to);
}
bool judge(){
int cnt = 0;
queue<int> que;
//拓扑排序
for(int i = 0; i < N; ++i)
if(!ind[i]){
que.push(i);
cnt++;
}
while(!que.empty()){
int u = que.front(); que.pop();
for(int i = 0; i < G[u].size(); ++i){
int to = G[u][i];
ind[to]--;
for(int j = 0; j < 26; ++j)
d[to][j] = max(d[to][j], d[u][j]+(j == (node[to]-'a')));
//若下一点的字母与当前字母相同则下一点的此字母等于当前点此字母+1
if(!ind[to]){
cnt++;
que.push(to);
}
}
}
if(cnt != N)
return false;
return true;
}
void solve(){
int maxlen = 0;
if(!judge())
cout << -1 << endl;
else{
for(int i = 0; i < N; ++i)
for(int j = 0; j < 26; ++j){
if(maxlen < d[i][j]){
maxlen = d[i][j];
}
}
cout << maxlen << endl;
}
}
int main(){
//fre;
cin >> N >> M;
cin >> node;
for(int i = 0; i < N; ++i)
d[i][node[i]-'a']++; // 初始化
for(int i = 0; i < M; ++i){
int f,t;
cin >> f >> t;
f--; t--;
ind[t]++; //入度+1
add(f,t);
}
solve();
return 0;
}

最后

以上就是繁荣火龙果为你收集整理的codeforces 919D Substring(简单dp)的全部内容，希望文章能够帮你解决codeforces 919D Substring(简单dp)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。