CF919D Substring (dag dp)

解题思路

　　感觉这种题都是套路，首先缩点判了环(没看见自环挂了一次。。)，然后设\(f[x][i]\)表示到了\(x\)，\(i\)这个字母走过的最长距离，然后拓扑排序更新即可。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<queue>

using namespace std;

const int MAXN = 300005;

inline int rd(){

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}

	while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

	return f?x:-x;

} 

int n,m,head[MAXN],cnt,dfn[MAXN],low[MAXN],num,w[MAXN],ans;

int to[MAXN],nxt[MAXN],f[MAXN][30],stk[MAXN],top,deg[MAXN];

bool vis[MAXN],flag;

char s[MAXN];

queue<int> Q;

inline void add(int bg,int ed){

	to[++cnt]=ed,nxt[cnt]=head[bg],head[bg]=cnt;

}

void tarjan(int x){

	dfn[x]=low[x]=++num;stk[++top]=x;vis[x]=1;

	for(register int i=head[x];i;i=nxt[i]){

		int u=to[i];

		if(!dfn[u]) {tarjan(u);low[x]=min(low[x],low[u]);}

		else if(vis[u]) low[x]=min(low[x],dfn[u]);

	}

	if(low[x]==dfn[x]) {

		if(stk[top]!=x) {flag=1;return;}

		top--;vis[x]=0;

	}

}

int main(){

	n=rd(),m=rd();int x,y;

	scanf("%s",s+1);

	for(int i=1;i<=n;i++) w[i]=s[i]-'a'+1;

	for(int i=1;i<=m;i++){

		x=rd(),y=rd();deg[y]++;

		if(x==y) flag=1;

		add(x,y);

	}

	for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);

	if(flag) {puts("-1");return 0;}

	else{

		for(int i=1;i<=n;i++) if(!deg[i]) Q.push(i),f[i][w[i]]=1;

		while(Q.size()){

			int x=Q.front();Q.pop();

			for(register int i=head[x];i;i=nxt[i]){

				int u=to[i];

				f[u][w[u]]=max(f[u][w[u]],f[x][w[u]]+1);

				for(int k=1;k<=26;k++) if(w[u]!=k) f[u][k]=max(f[u][k],f[x][k]);

				deg[u]--;if(!deg[u]) Q.push(u);

			}

			if(!head[x]) for(int i=1;i<=26;i++) ans=max(ans,f[x][i]);

		}

	}

	printf("%d\n",ans);

	return 0;

}

巴特西

CF919D Substring (dag dp)

解题思路

代码

最新文章

热门文章