cf815C

题意:

  有n件商品,每件有价格c[i],优惠券d[i],

   对于i>=2,使用di的条件为:xi的优惠券需要被使用,问初始金钱为b时 最多能买多少件商品? n<=5000

解答

树上背包

f[u][j][0/1] 表示某子树(u)有体积j（分配的物品数目) ，该物品是否选择，所需要的最小金钱

f[u][j][1]=min{ min(f[y][k][1],f[y][k][0]) + f[u][j-k][1] }

程序采用刷表法（填表法会超时，痛苦

#include <iostream>
#include <cstring>
using namespace std;
const int N=5005;
#define int long long
int all,hd[N],go[N],nxt[N];
void add(int x,int y){
go[++all]=y; nxt[all]=hd[x]; hd[x]=all;
}
int w[N],a[N],n,m,f[N][N][2];
int sz[N];
void dp(int u){
int e,j,k;
f[u][0][0]=0;
f[u][1][0]=w[u];
f[u][1][1]=w[u]-a[u];
sz[u]=1;
for(e=hd[u];e;e=nxt[e]){
int y=go[e]; dp(y);
for(j=sz[u];j>=0;j--)
for(k=0;k<=sz[y];k++){
f[u][j+k][0]=min(f[u][j+k][0],f[u][j][0]+f[y][k][0]);
f[u][j+k][1]=min(f[u][j][1]+min(f[y][k][0],f[y][k][1]),f[u][j+k][1]);
}
sz[u]+=sz[y];
}
}
const int inf=0x3f3f3f3f;
signed main(){
cin>>n>>m;
int i,j,x,y;
for(i=1;i<=n;i++){
scanf("%d%d",w+i,a+i);
if(i>1) scanf("%d",&x),add(x,i);
}
memset(f,inf,sizeof f);
dp(1);
for(j=n;j>=0;j--){
if(f[1][j][0]<=m||f[1][j][1]<=m){
printf("%d",j) ;break;
}
}
}

最后

以上就是机灵小天鹅为你收集整理的cf815C的全部内容，希望文章能够帮你解决cf815C所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。