bzoj 3090: Coci2009 [podjela]

题意：

有$N$个农民, 他们住在$N$个不同的村子里. 这$N$个村子形成一棵树.
每个农民初始时获得$X$的钱.
每一次操作, 一个农民可以从它自己的钱中, 取出任意数量的钱, 交给某个相邻村子的农民.
对于每个农民给定一个值$v_i$, 求最少需要多少次操作, 使得每个农民最终拿到的钱$\ge$给定的值.

题解：

一开始想了一个很不靠谱的东西，$f_{i, j}$表示$i$的子树往上给（拿）$j$元钱的最小操作数，然后发现时空两爆炸，于是膜了个状态。
正解的状态是$f_{i, j}$表示$i$的子树操作$j$次最多网上给（拿）多少钱。转移就树上背包就好了。

代码：

#include <bits/stdc++.h>
using namespace std;

const int inf = 0x3f3f3f3f;
int n, X, a[2010], sz[2010], num = 0, fst[2010], f[2010][2010];
struct edge
{
    int x, y, n;
} e[4010];

void ins(int x, int y)
{
    e[++num] = {x, y, fst[x]};
    fst[x] = num;
}
void dfs(int x, int fa)
{
    sz[x] = 1;
    f[x][0] = X - a[x];
    for (int i = fst[x]; i; i = e[i].n)
    {
        int y = e[i].y;
        if (y == fa) continue;
        dfs(y, x);
        sz[x] += sz[y];
        for (int i = sz[x] - 1; i >= 0; i--)
        {
            int hh = -inf;
            for (int j = 0; j < sz[y]; j++)
            {
                if (j <= i && f[y][j] >= 0) hh = max(hh, f[x][i - j]);
                if (j < i) hh = max(hh, f[x][i - j - 1] + f[y][j]);
            }
            f[x][i] = hh;
        }/*
        printf("%d\n", x);
        for (int i = 0; i < sz[x]; i++)
            printf("%d ", f[x][i]);
        puts("");*/
    }
}
int main()
{
    scanf("%d%d", &n, &X);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i < n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        ins(x, y);
        ins(y, x);
    }
    memset(f, -63, sizeof(f));
    dfs(1, 0);
    for (int i = 0; i < n; i++)
        if (f[1][i] >= 0)
        {
            printf("%d\n", i);
            return 0;
        }
    assert(0);
}