社区讨论

help

P10287[GESP样题 七级] 最长不下降子序列参与者 2已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@mhjs6o8s
此快照首次捕获于
2025/11/04 07:38
4 个月前
此快照最后确认于
2025/11/04 07:38
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,ans;
int a[N],d[N],dp[N][20];
vector<int> g[N];
queue<int> q;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        d[v]++;
    }
    for(int i=1;i<=n;i++){
        
        if(!d[i]){
            q.push(i);
            dp[i][a[i]]=1;
        }
    }
    while(q.size()){
        int t=q.front();
        q.pop();
        for(auto u:g[t]){
            d[u]--;
            if(!d[u]) q.push(u);
            if(a[u]>=a[t]) dp[u][a[u]]=dp[t][a[t]]+1;
            else dp[u][a[u]]=max(dp[u][a[u]],dp[t][a[t]]);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=10;j++){
            ans=max(ans,dp[i][j]);
        }
    }
    cout<<ans;
    return 0;
}

回复

3 条回复,欢迎继续交流。

正在加载回复...