题目链接
题目思路
算是两个经典问题的结合
首先看到问题描述可以转换为分组背包
看到\(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;
}