题解 | 小红的双生英雄

好几个代码应该是有问题的

都是直接单人dp一遍  双人dp一遍  

没有考虑到使用双生时 其中的英雄已经使用过的情况

下面的样例 输出应该为 30 

2 40 1
5 10
5 10
1 2 10

应当将双生的两个英雄作为一个整体考虑

直接四种情况一起转移

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define C getchar()-48
inline ll read(){
    ll s=0,r=1;
    char c=C;
    for(;c<0||c>9;c=C) if(c==-3) r=-1;
    for(;c>=0&&c<=9;c=C) s=(s<<3)+(s<<1)+c;
    return s*r;
}
#define rep(i,sti,edi) for(int i=sti;i<=edi;i++)
const int N=1e3+10;
int n,cost,m;
ll dp[3][6][N];
struct xin{
    ll cost=0,v=0,tp=0,fnv=0;
}a[N];
int main(){
    n=read(),cost=read(),m=read();
    rep(i,1,n) a[i].cost=read(),a[i].v=read();
    rep(i,1,m){
        int x=read(),y=read();ll v=read();
        a[x].tp=y;a[y].tp=x;
        a[x].fnv=a[y].fnv=v;
    }
    rep(i,1,n){
        int dqkd=i&1;int qmkd=dqkd^1;
        int tpi=a[i].tp;
        rep(k,0,4) rep(j,0,cost) 
            dp[dqkd][k][j]=dp[qmkd][k][j];
        if(tpi&&tpi<i) continue;
        rep(k,1,4) rep(j,a[i].cost,cost) 
            dp[dqkd][k][j]=max(dp[dqkd][k][j],dp[qmkd][k-1][j-a[i].cost]+a[i].v);
        if(!tpi) continue;
        rep(k,1,4) rep(j,a[tpi].cost,cost) 
            dp[dqkd][k][j]=max(dp[dqkd][k][j],dp[qmkd][k-1][j-a[tpi].cost]+a[tpi].v);
        rep(k,2,4) rep(j,a[i].cost+a[tpi].cost,cost) 
            dp[dqkd][k][j]=max(dp[dqkd][k][j],dp[qmkd][k-2][j-a[i].cost-a[tpi].cost]+a[i].v+a[tpi].v+a[i].fnv);      
    }
    ll ans=0;
    rep(k,0,4) ans=max(ans,dp[n&1][k][cost]); 
    cout<<ans;
    return 0;
}