问题描述
On the way home, Karen decided to stop by the supermarket to buy some groceries.
She needs to buy a lot of goods, but since she is a student her budget is still quite limited. In fact, she can only spend up to b dollars.
The supermarket sells n goods. The i-th good can be bought for ci dollars. Of course, each good can only be bought once.
Lately, the supermarket has been trying to increase its business. Karen, being a loyal customer, was given n coupons. If Karen purchases the i-th good, she can use the i-th coupon to decrease its price by di. Of course, a coupon cannot be used without buying the corresponding good.
There is, however, a constraint with the coupons. For all i?≥?2, in order to use the i-th coupon, Karen must also use the xi-th coupon (which may mean using even more coupons to satisfy the requirement for that coupon).
Karen wants to know the following. What is the maximum number of goods she can buy, without exceeding her budget b?
输入格式
The first line of input contains two integers n and b (1?≤?n?≤?5000, 1?≤?b?≤?109), the number of goods in the store and the amount of money Karen has, respectively.
The next n lines describe the items. Specifically:
- The i-th line among these starts with two integers, ci and di (1?≤?di?<?ci?≤?109), the price of the i-th good and the discount when using the coupon for the i-th good, respectively.
- If i?≥?2, this is followed by another integer, xi (1?≤?xi?<?i), denoting that the xi-th coupon must also be used before this coupon can be used.
输出格式
Output a single integer on a line by itself, the number of different goods Karen can buy, without exceeding her budget.
样例输入
6 16
10 9
10 5 1
12 2 1
20 18 3
10 2 3
2 1 5
样例输出
4
题目大意
在回家的路上，凯伦决定到超市停下来买一些杂货。 她需要买很多东西，但因为她是学生，所以她的预算仍然很有限。
事实上，她只花了b美元。
超市出售N种商品。第i件商品可以以ci美元的价格购买。当然，每件商品只能买一次。
最近，超市一直在努力促销。凯伦作为一个忠实的客户，收到了n张优惠券。
如果 Karen 购买第 i件商品，她可以使用第 i张优惠券，将该商品的价格减少 d_i美元。 当然，不买对应的商品，优惠券不能使用。
然而，对于优惠券有一个规则。对于所有i>=2，为了使用i张优惠券，凯伦必须也使用第xi张优惠券 （这可能意味着使用更多优惠券来满足需求。）
凯伦想知道。她能在不超过预算B的情况下购买的最大商品数量是多少？
解析
显然是一道有依赖的背包问题，直接树形DP来做。观察到b的范围达到了1e9，所以不能按照常规的方式来设计状态。设\(f[i][j][0/1]\)表示在以i为根的子树中选择了j样商品的价格，0表示没有使用折扣，1表示使用了折扣。那么，我们有如下状态转移方程：
\[ f[u][j+k][0]=max(f[u][j][0]+f[v][k][0])\f[u][j+k][1]=max(f[u][j][1]+f[v][k][1],f[u][j][1]+f[v][k][0]) \]
最后答案即为满足\(min(f[1][i][0],f[1][i][1])<=b\)的最大的i。
这里还要注意以下两点：
- 直接这样做是\(n^3\)的。因此，我们要剪掉一些无用的枚举。观察DP方程，其实k的范围只有0到size[v]，而j的范围则是0到当前的size[x] (即v之前的子树大小之和加上u本身)。因为子节点的容量只有这么多，而父节点更新时只需要与前面已经得到的答案进行比较。因此复杂度可以降至\(n^2\)。
- 注意转移的更新顺序。要做到不重复更新，具体顺序见代码。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#define int long long
#define N 5002
using namespace std;
int head[N],ver[N*2],nxt[N*2],l;
int n,b,i,c[N],d[N],size[N],f[N][N][2],ans;
int read()
{
char c=getchar();
int w=0;
while(c<'0'||c>'9') c=getchar();
while(c<='9'&&c>='0'){
w=w*10+c-'0';
c=getchar();
}
return w;
}
void insert(int x,int y)
{
l++;
ver[l]=y;
nxt[l]=head[x];
head[x]=l;
}
void dp(int x,int pre)
{
f[x][0][0]=0;
f[x][1][0]=c[x];
f[x][1][1]=c[x]-d[x];
size[x]=1;
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
if(y!=pre){
dp(y,x);
for(int j=size[x];j>=0;j--){
for(int k=0;k<=size[y];k++){
f[x][j+k][0]=min(f[x][j+k][0],f[x][j][0]+f[y][k][0]);
f[x][j+k][1]=min(f[x][j+k][1],f[x][j][1]+f[y][k][0]);
f[x][j+k][1]=min(f[x][j+k][1],f[x][j][1]+f[y][k][1]);
}
}
size[x]+=size[y];
}
}
}
signed main()
{
memset(f,0x3f,sizeof(f));
n=read();b=read();
for(i=1;i<=n;i++){
c[i]=read(),d[i]=read();
if(i>=2){
int x=read();
insert(x,i);
}
}
dp(1,0);
for(i=n;i>=1;i--){
if(f[1][i][0]<=b||f[1][i][1]<=b){
printf("%d\n",i);
return 0;
}
}
puts("0");
return 0;
}