# Karen and Supermarket

## 题目描述

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 $c_i$ 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 $d_i$. Of course, a coupon cannot be used without buying the corresponding good.
There is, however, a constraint with the coupons. For all $i \ge 2$, in order to use the $i$-th coupon, Karen must also use the $x_i$-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$?

## 算法分析

$$s_i=1, \; f_{i, 0, 0}=0, \; f_{i, 1, 0}=c_i, \; f_{i, 1, 1}=c_i-d_i$$

\begin{align} f_{i, j + k, 0}&=\min(f_{i, j, 0} + f_{u, k, 0}) \\ f_{i, j + k, 1}&=\min(f_{i, j, 1} + \min(f_{u, k, 0}, f_{u, k, 1})) \end{align}

## 代码

#include <iostream>
#include <cstring>
using namespace std;
struct edge {
int v, nxt;
} e[5001];
long long n, b, tot, h[5001], c[5001], d[5001], x, s[5001], f[5001][5001][2];
void add_edge(int u, int v) {
e[++tot].v = v;
e[tot].nxt = h[u];
h[u] = tot;
}
void dfs(int t) {
for (int k = h[t]; k; k = e[k].nxt) {
dfs(e[k].v);
for (int i = s[t]; i >= 0; --i) {
for (int j = 0; j <= s[e[k].v]; ++j) {
f[t][i + j][0] = min(f[t][i + j][0], f[t][i][0] + f[e[k].v][j][0]);
f[t][i + j][1] = min(f[t][i + j][1], f[t][i][1] + min(f[e[k].v][j][0], f[e[k].v][j][1]));
}
}
s[t] += s[e[k].v];
}
}
int main()
{
cin >> n >> b;
memset(f, 0x7f, sizeof(f));
for (int i = 1; i <= n; ++i) {
cin >> c[i] >> d[i];
s[i] = 1;
f[i][0][0] = 0;
f[i][1][0] = c[i];
f[i][1][1] = c[i] - d[i];
if (i - 1) {
cin >> x;
}
}
dfs(1);
for (int i = n; i >= 0; --i) {
if (min(f[1][i][0], f[1][i][1]) <= b) {
cout << i << endl;
break;
}
}
return 0;
}


418 I'm a teapot