CSUST 黄金矿工 题解(分组背包+转换dp方程状态)

题目链接

题目思路

算是两个经典问题的结合

首先看到问题描述可以转换为分组背包

看到\(t\)很大,所以设\(dp[i]\)表示达到价值为\(i\)的最少时间是多少,然后\(dp\)即可

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
#define fi first
#define se second
#define debug printf("aaaaaaaaaaa\n");
const int maxn=2e2+100,inf=0x3f3f3f3f,mod=1e9+7;
const ll INF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-7;
int n,sum;
int v[maxn],t[maxn],f[maxn];
int son[maxn],fa[maxn];
vector<pii> vec[maxn];
ll dp[10000+5];
int main(){
    int _; scanf("%d",&_);
    while(_--){
        scanf("%d%d",&n,&sum);
        for(int i=1;i<=n;i++){
            fa[i]=son[i]=0;
            vec[i].clear();
        }
        for(int i=1;i<=n;i++){
            scanf("%d%d%d",&v[i],&t[i],&f[i]);
            son[f[i]]=i;
            fa[i]=f[i];
        }
        int cnt=0;
        for(int i=1;i<=n;i++){
            if(fa[i]!=0) continue;
            cnt++;
            int x=i;
            int tempv=0,tempt=0;
            while(x){
                tempv+=v[x];
                tempt+=t[x];
                vec[cnt].push_back({tempv,tempt});
                x=son[x];
            }
        }
        memset(dp,0x3f,sizeof(dp));
        dp[0]=0;
        for(int i=1;i<=cnt;i++){
            for(int j=10000;j>=0;j--){
                for(int k=0;k<vec[i].size();k++){
                    int x=vec[i][k].fi,y=vec[i][k].se;
                    if(j>=x){
                        dp[j]=min(dp[j],dp[j-x]+y);
                    }
                }
            }
        }
        for(int i=10000;i>=0;i--){
            if(dp[i]<=sum){
                printf("%d\n",i);
                break;
            }
        }
    }
    return 0;
}