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$?

题意概述

有$n$件商品，第$i$件商品的价格为$c_i$。同时，第$i$件商品有一张可以将价格降低$d_i$的优惠券，使用这张优惠券的前提是第$x_i$件商品的优惠券也被使用（使用优惠券后必须买对应的商品；第一件商品的优惠券没有使用前提）。问在总价格不超过$b$的情况下最多能购买多少商品。

数据范围：$1 \le n \le 5000, \ 1 \le b \le 10^9, \ 1 \le d_i \lt c_i \le 10^9, \ 1 \le x_i \lt i$。

算法分析

很明显这是一棵树。

令$s_i$表示第$i$件商品已处理过的子树大小，$f_{i, j, 1/0}$表示从第$i$件商品以及它的子树中购买$j$件商品且第$i$件商品使用/不使用优惠券时的最少价格。初始时

$$
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}
$$

转移时需要满足$u$是$i$的儿子，且$0 \le j \le s_i, \ 0 \le k \le s_u$。

代码

#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;
            add_edge(x, i);
        }
    }
    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;
}