题解：P16701 [MCO 2026] 制造连招

· · 题解

题目传送门

思路

放在 NOIP 模拟赛第二题位置属实是简单了。但是应该也有青蓝的难度。

读完题要想到 dp，我们关注到这句话：

题目保证输入中的技能连接不会形成环。

所以思路就显然了。考虑 dp 状态的定义，影响答案构成的无非就是以下 4 个量：

考虑定义 f_{u,i,j,0/1} 表示上面的四个量。转移到有边 (u,v) 的 v，分类讨论 v 用不用外挂。这样转移就没了。

注意转移顺序要拓扑排一下，不能有后效性。

发现 k 很大。但是你的 B 每次翻倍达到 10^9 只需要 30 次啊。所以有效的 k 最大是 30。直接取 \min 即可。

时间复杂度 O(n\log^2V)。

代码

::::info[Code]

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5,inf=1e9;
int n,m,k,t,d[N],c[N],du[N],dp[N][31][31][2],ans;
vector <int> g[N],sx;
void topo_sort(){
    queue <int> q;
    for(int i=1;i<=n;i++) if(!du[i]) q.push(i);
    while(!q.empty()){
        int u=q.front();q.pop();
        sx.push_back(u);
        for(auto v:g[u]) if(--du[v]==0) q.push(v);
    }
}
signed main(){
    scanf("%d%d%d%d",&n,&m,&k,&t);k=min(k,30);
    for(int i=1;i<=n;i++) scanf("%d%d",d+i,c+i);
    for(int i=1,u,v;i<=m;i++){
        scanf("%d%d",&u,&v);
        u++,v++;
        g[u].push_back(v),du[v]++;
    }
    memset(dp,-1,sizeof(dp));
    for(int u=1;u<=n;u++){
        dp[u][0][1][0]=d[u];
        if(c[u]!=t&&k>=1) dp[u][1][1][1]=d[u];
    }
    topo_sort();
    for(auto u:sx){
        for(int i=0;i<=k;i++){
            for(int j=1;j<=29;j++){
                for(int op=0;op<=1;op++){
                    if(dp[u][i][j][op]==-1) continue;
                    int col=c[u];
                    if(op==1) col=t;
                    for(auto v:g[u]){
                        if(c[v]==col){
                            if(j==29) return printf("-1"),0;
                            long long val=dp[u][i][j][op]+d[v]*(1ll<<j);
                            if(val>inf) return printf("-1"),0;
                            dp[v][i][j+1][0]=max(dp[v][i][j+1][0],(int)val);
                        }
                        else{
                            long long val=dp[u][i][j][op]+d[v];
                            if(val>inf) return printf("-1"),0;
                            dp[v][i][1][0]=max(dp[v][i][1][0],(int)val);
                        }
                        if(c[v]!=t&&i+1<=k){
                            if(col==t){
                                if(j==29) return printf("-1"),0;
                                long long val=dp[u][i][j][op]+d[v]*(1ll<<j);
                                if(val>inf) return printf("-1"),0;
                                dp[v][i+1][j+1][1]=max(dp[v][i+1][j+1][1],(int)val);
                            }
                            else{
                                long long val=dp[u][i][j][op]+d[v];
                                if(val>inf) return printf("-1"),0;
                                dp[v][i+1][1][1]=max(dp[v][i+1][1][1],(int)val);
                            }
                        }
                    }
                }
            }
        }
    }
    for(int u=1;u<=n;u++)
        for(int i=0;i<=k;i++)
            for(int j=1;j<=30;j++)
                ans=max({ans,dp[u][i][j][0],dp[u][i][j][1]});
    printf("%d",ans);
    return 0;
}

:::: 撒花！