【DAG上DP】字符王国

短命女 2024-03-22 09:44 8阅读 0赞

[题目-字符王国 (51nod.com)][-_ _51nod.com]

题意：

![0bb6cfa73e164377997d74b535a83435.png][]

思路：

直接DP

设dp\[i\]\[j\]为以结点i为终点，多起点到结点i的这么多条路径中字符j的最大出现次数

然后直接转移就行

注意和线性DP一样需要先枚举状态再枚举决策，阶段在拓扑排序的时候就枚举好了

Code：

#include <bits/stdc++.h>
    
    //#define int long long
    
    using namespace std;
    
    const int mxn=3e5+10;
    const int mxe=3e5+10;
    const int Inf=0x3f3f3f3f;
    
    struct ty{
    	int to,next;
    }edge[mxe<<1];
    
    int n,m,u,v,ans=-Inf,tot=0;
    int a[mxn],in[mxn],dp[mxn][30],head[mxn];
    string s;
    
    void G_init(){
    	tot=0;
    	for(int i=0;i<=n;i++){
    		head[i]=-1;
    	}
    }
    void topsort(){
    	queue<int> q;
    	for(int i=1;i<=n;i++){
    		if(!in[i]){
    			q.push(i);
    			dp[i][a[i]]=1;
    		}
    	}
    	while(!q.empty()){
    		int u=q.front();
    		q.pop();
    		for(int i=head[u];~i;i=edge[i].next){
    			for(int j=1;j<=26;j++){
    				if(a[edge[i].to]==j) dp[edge[i].to][j]=max(dp[edge[i].to][j],dp[u][j]+1);
    				else dp[edge[i].to][j]=max(dp[edge[i].to][j],dp[u][j]);
    			}
    			in[edge[i].to]--;
    			if(!in[edge[i].to]) q.push(edge[i].to);
    		}
    	}
    }
    void add(int u,int v){
    	edge[tot].to=v;
    	edge[tot].next=head[u];
    	head[u]=tot++;
    }
    void solve(){
    	cin>>n>>m;
    	G_init();
    	cin>>s;
    	s=" "+s;
    	for(int i=1;i<=n;i++) a[i]=s[i]-'a'+1;
    	for(int i=1;i<=m;i++){
    		cin>>u>>v; 
    		add(u,v);
    		in[v]++;
    	}
    	topsort();
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=26;j++) ans=max(ans,dp[i][j]); 
    	}
    	cout<<ans<<'\n';
    }
    signed main(){
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[-_ _51nod.com]: http://www.51nod.com/Challenge/Problem.html#problemId=3188
[0bb6cfa73e164377997d74b535a83435.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/e3a35fc9e08042979af1634d371adfe4.png