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

· · 题解

:::info[P话] 模拟赛T2，但是感觉这题不止绿。 :::

思路

考虑 DAG 上的 DP，我们设 f_{i,k,l,p}(p\in \{0,1\}) 表示最大的伤害值，我来介绍一下每一维表示什么。

我们用优美的语文把上面那四条给拼接起来就是 f_{i,k,l,p} 表示以 i 为终点用了 k 次挂长度为 l 的同色链同时 0 表示不改色，1 表示改色的最大伤害值。

那么转移我们来讨论一下：

如果不改色的情况：

如果 c_u=c_v 那么就有：

f_{v,k,l+1,0}=\max\{f_{u,k,l,p}+2^l\times d_v\}

否则：

f_{v,k,1,0}=\max\{f_{u,k,l,p}+d_v\}

改色的情况：

如果 c_v=t 那么就有：

f_{v,k,l+1,1}=\max\{f_{u,k,l,p}+d_v\times 2^l\}

否则：

f_{v,k,1,1}=\max\{f_{u,k,l,p}+d_v\}

注意我们在 p=1 的时候 c_u=t。

:::success[代码]

const int N = 1e4 + 10;
int n,m,t,K;
int c[N];
vector<int>g[N];
ll d[N],dp[N][65][65][2];
int indu[N],outdu[N];
void solve(){
    cin>>n>>m>>K>>t;
    for(int i = 1;i <= n;++i) cin>>d[i]>>c[i];
    for(int i = 1;i <= m;++i){
        int u,v;
        cin>>u>>v;
        u++,v++;
        indu[v]++;
        g[u].pb(v);
    }
    for(int i = 1; i <= n; ++i)for(int k = 0; k <= 32; ++k)for(int l = 1; l <= 32; ++l)dp[i][k][l][0] = dp[i][k][l][1] = -1;
    K = min(K, 30); 
    for(int i = 1;i <= n;++i){
        dp[i][0][1][0] = d[i];
        if(c[i] != t) dp[i][1][1][1] = d[i];
    }
    queue<int>q;
    for(int i = 1;i <= n;++i){
        if(indu[i] == 0) q.push(i);
    }
    ll ans = 0;
    bool flag = false;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int k = 0;k <= K;++k){
            for(int p = 0;p <= 1;++p){
                for(int l = 1;l <= 31;++l){
                    ll val = dp[u][k][l][p];
                    if(val == -1) continue;
                    ans = max(ans, val);
                    int cn = p ? t : c[u];
                    for(int v:g[u]){
                        if(c[v] == cn) {
                            if(l < 31) {
                                ll tw = val + d[v] * (1LL << l); 
                                if(tw > 1e9) flag = true;
                                else dp[v][k][l + 1][0] = max(dp[v][k][l + 1][0], tw);
                            } else flag = true;
                        } else {
                            ll tw = val + d[v];
                            if(tw > 1e9) flag = true;
                            else dp[v][k][1][0] = max(dp[v][k][1][0], tw);
                        }
                        if(c[v] != t && k < K){
                            if(t == cn) { 
                                if(l < 31) {
                                    ll tw = val + d[v] * (1LL << l);
                                    if(tw > 1e9) flag = true;
                                    else dp[v][k + 1][l + 1][1] = max(dp[v][k + 1][l + 1][1], tw);
                                } else flag = true;
                            } else { 
                                ll tw = val + d[v];
                                if(tw > 1e9) flag = true;
                                else dp[v][k + 1][1][1] = max(dp[v][k + 1][1][1], tw);
                            }
                        }
                    }
                }
            }
        }
        for(int v:g[u]){
            indu[v]--;
            if(indu[v] == 0) q.push(v);
        }
    }
    if(flag || ans > 1e9) cout<<-1<<"\n";
    else cout<<ans<<"\n";
}

:::