3188 字符王国
题意： 给出一个 n 个点 m 条边的有向图，每个点上有一个字母。
问图中的路径上出现次数最多的字母 出现的次数 为多少？
分析： 一开始想把所有的字母放在一起更新状态，但是状态不好转移。
定义：
f[i, j]：到位置 i 时，字母 j 最多出现的次数。
状态转移：
对于每个位置，分别遍历更新 26 个字母：
- 如果转移过来位置的字母和当前字母相同的话：
f[tx][i] = max(f[tx][i], f[x][i]+1); - 否则：
f[tx][i] = max(f[tx][i], f[x][i]);
（x为当前点，tx为邻接点）
Code：
//http://www.51nod.com/Challenge/Problem.html#problemId=3188
#include
using namespace std;
#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define mem(a,b) memset(a,b,sizeof a)
#define int long long
#define PII pair
#define pb push_back
#define fi first
#define se second
#define endl '\n'map mp;
const int N = 300010, mod = 1e9+7;
int T, n, m, k;
int a[N], ru[N];
int f[N][30];
vector e[N];
void topsort()
{
queue que;
for(int i=1;
i<=n;
i++)
if(!ru[i]) que.push(i), f[i][a[i]]=1;
while(que.size())
{
int x = que.front();
que.pop();
for(auto tx:e[x])
{
for(int i=1;
i<=26;
i++){
if(a[tx]==i) f[tx][i] = max(f[tx][i], f[x][i]+1);
else f[tx][i] = max(f[tx][i], f[x][i]);
}ru[tx]--;
if(ru[tx] == 0) que.push(tx);
}
}
}signed main(){
Ios;
cin>>n>>m;
for(int i=1;
i<=n;
i++)
{
char c;
cin>>c;
a[i] = c-'a'+1;
}
while(m--)
{
int x, y;
cin>>x>>y;
e[x].pb(y);
ru[y]++;
}
topsort();
int ans=0;
for(int i=1;
i<=n;
i++)
{
for(int j=1;
j<=26;
j++) ans = max(ans, f[i][j]);
}
cout< 推荐阅读
- #|蓝桥杯31天冲刺打卡题解（Day11）
- 模拟赛|2022.3.13模拟赛总结
- codeforce|Codeforces Round #774 (Div. 2) D. Weight the Tree
- 备战蓝桥杯|2020年第十一届蓝桥杯省赛Python组（真题+解析+代码）（作物杂交）
- 算法提高课|AcWing 1086 恨7不成妻
- 算法与数据结构|算法与数据结构——AcWing算法题常用代码模板
- dfs|LightOJ1030-Discovering Gold-dp
- ACM专题学习|小沙的算数--并查集 (联通块)
- 图论|通信线路「分层图最短路」||「二分答案 + 巧妙的建图跑最短路」