题解 CF919D 【Substring】
ZolaWatle
2020-08-18 19:40:59
# CF919D题解
容易发现，对于每一个点都只有一个状态，而且对于整张图最多只有26个状态（即所有小写字母的总数）。
再看数据范围，$ n $ 的范围 $ 3e5 $，搜索肯定是不行的。在状态数量那么小的情况下，状态是很好表示的。为了方便数组存储，可以用 $ idx_i = tmp - 'a\ ' + 1 $ 表示（$ tmp $ 是 $ i $ 号节点的字母）。这样一来，$ a - z $ 可以转化为 $ 1 - 26 $ 这26个数字。
我们考虑使用**DP**：开一个数组 $ dp_{i,j} $ 表示当走到 $ i $ 点时字母 $ j $ 的最大出现次数。当然，经过了前面的分析，$ j $ 是使用数字表示的。
应当在读入每个点的字母时初始化 dp 数组，使得路径 “ $ x -> x $ ” 上字母 $ idx_x $ 的出现次数为 $ 1 $。
由于这张图是**有向图**，为了满足动态规划的**无后效性**，考虑使用**拓扑排序**进行dp。
设当前操作是从节点 $ x $ 走向节点 $ y $，我们分两种情况考虑状态转移方程：
- 若 $ idx_y = j $，即节点 $ y $ 的字母和现在扫描到的字母相同，那么走到 $ y $ 后，这个字母的出现次数要加一。即：$ dp_{y,j} = max $ { $ dp_{y,j} , dp_{x,j} + 1 $ } 。
- 同理，若字母不同，次数不必加一。即：$ dp_{y,j} = max $ { $ dp_{y,j} , dp_{x,j} $ } 。
在进行拓扑排序时进行状态转移即可。
当然，还要考虑输出 $ -1 $ 的情况。可在拓扑排序过程中开一个计数器 $ sum $，每有一个元素出队就加一，最后判断它是否小于 $ n $，如果小于，则说明有环，输出 $ -1 $ 就行了。
完整代码如下（详情见注释）：
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#define re register int
using namespace std;
const int MAXN=3e5+1;
int n,m,ans,sum,idx[MAXN],in[MAXN],dp[MAXN][27];
vector <int> E[MAXN];
queue <int> q;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int main()
{
n=read(),m=read();
for(re i=1;i<=n;i++)
{
char tmp=getchar(); //这样读入速度更快
idx[i]=tmp-'a'+1; //也可以写tmp-95
dp[i][idx[i]]++; //初始化
}
for(re i=1;i<=m;i++)
{
re x=read(),y=read();
E[x].push_back(y); //用vector存边
in[y]++; //统计入度
}
for(re i=1;i<=n;i++)
if(!in[i])
q.push(i);
while(!q.empty())
{
re x=q.front();
q.pop();
in[x]=-1; //删点
sum++;
for(re i=0;i<E[x].size();i++)
{
re y=E[x][i];
for(re j=1;j<=26;j++)
{
if(idx[y]==j)
dp[y][j]=max(dp[y][j],dp[x][j]+1);
else
dp[y][j]=max(dp[y][j],dp[x][j]);
}//状态转移
in[y]--;
if(!in[y])
q.push(y);
}
}//拓扑基本操作
if(sum<n)
{
printf("-1");
return 0;
}//The value can be arbitrarily large
for(re i=1;i<=n;i++)
for(re j=1;j<=26;j++)
ans=max(ans,dp[i][j]); //由于这条路径可以在任意点出发，任意点结束，因此在dp完毕后还要像这样计算答案
printf("%d",ans);
return 0;
}
```
谢谢观看~