比赛 树立信心的模拟赛 评测结果 WWWWWWWWWW
题目名称 凯伦和超市 最终得分 0
用户昵称 Shirry 运行时间 1.016 s
代码语言 C++ 内存使用 191.97 MiB
提交时间 2017-09-01 21:59:25
显示代码纯文本
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm> 
using namespace std;
const int maxn=5010;
int n,m,b[maxn],c[maxn],d[maxn],x[maxn],f[2][maxn][maxn];
int son[maxn];
vector<int>edge[maxn];
int dfs(int x,int y){
	son[x]=1;
	f[1][x][0]=0;
	f[1][x][1]=c[x];//不用优惠券
	f[0][x][1]=c[x]-b[x];//用优惠券
	for(int k=0;k<(int)edge[x].size();k++){
		int p=edge[x][k];
		if(p==y)continue;
		dfs(p,x);
		for(int i=son[x];i>=0;i--){
			for(int j=son[p];j>=0;j--){
				f[0][x][i+j]=min(f[0][x][i+j],f[0][x][i]+min(f[1][p][j],f[0][p][j]));
				f[1][x][i+j]=min(f[1][x][i+j],f[1][x][i]+f[1][p][j]);
			}
		}
		son[x]+=son[p];
	}
}
int main(){
	freopen("market.in","r",stdin);
	freopen("market.out","w",stdout);
	scanf("%d%d",&n,&b);
	memset(son,0,sizeof(son));
	memset(f,0x3f3f3f,sizeof(f));
	int t;
	for(int i=1;i<=n;i++){
		scanf("%d%d",&c[i],&b[i]);
		if(i>=2)scanf("%d",&t),edge[t].push_back(i);
	}
	dfs(1,-1);
	for(int i=n;i>=0;i--){
		long long minn=min(f[1][1][i],f[0][1][i]);
		if(minn<=m){
			printf("%d\n",i);
			break;
		}
	}
	return 0;
}