BZOJ 3090: Coci2009 [podjela] (树形背包)

3090: Coci2009 [podjela]

Time Limit: 3 Sec Memory Limit: 128 MB
Submit: 45 Solved: 31
[Submit][Status][Discuss]

Description

有 N 个农民, 他们住在 N 个不同的村子里. 这 N 个村子形成一棵树.
每个农民初始时获得 X 的钱.
每一次操作, 一个农民可以从它自己的钱中, 取出任意数量的钱, 交给某个相邻村子的农民.

对于每个农民给定一个值 v_i, 求
(1) 最少需要多少次操作, 使得每个农民最终拿到的钱 >= 给定的值.

Input

    第1行: 一个整数 N (1 <= N <= 2000)
    第2行: 一个整数 X (0 <= X <= 10000)
    第3行: N 个整数, 表示 v_i. 保证所有 v_i 的和 <= N * X
    第4..N+2行: 每行两个 1..N 的数, 表示树上的一条边. 边是双向的.

Output

第1行: 一个整数, 最少需要的操作次数

Sample Input

6
15
10 20 18 16 6 16
1 4
4 5
4 6
6 2
5 3

Sample Output

解题思路

树形背包，设dp[x][i]表示以x为根的子树，操作了i次，目前能给出/索要的钱数。u为x的儿子，如果dp[u][k]<0，说明这条边必须连，dp[x][j+k+1]=dp[x][j]+dp[u][k]，否则可以不连，dp[x][j+k]=dp[x][j]

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;
const int MAXN = 2005;
const int inf = -0x3f3f3f3f;

inline int rd(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}
    while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return f?x:-x;
}

int n,st,val[MAXN],head[MAXN],cnt,dp[MAXN][MAXN],siz[MAXN];
int to[MAXN<<1],nxt[MAXN<<1];

inline void add(int bg,int ed){
    to[++cnt]=ed,nxt[cnt]=head[bg],head[bg]=cnt;
}

void dfs(int x,int fa){
    int u,k,tmp;dp[x][0]=st-val[x];siz[x]=1;
    for(register int i=head[x];i;i=nxt[i]){
        u=to[i];if(u==fa) continue;dfs(u,x);
        for(k=0;k<siz[u] && dp[u][k]==inf;k++);
        for(register int j=siz[x];j<siz[x]+siz[u];j++) dp[x][j]=inf;
        for(register int j=siz[x]-1;j>=0;j--){
            tmp=dp[x][j];dp[x][j]=inf;
            if(tmp==inf) continue;
            for(register int o=k;o<siz[u];o++) {
                if(dp[u][o]==inf) continue;
                dp[x][j+o+1]=max(dp[x][j+o+1],tmp+dp[u][o]);
                if(dp[u][o]<0) continue;
                dp[x][j+o]=max(dp[x][j+o],tmp);
            }
        }
        siz[x]+=siz[u];
    }
}

int main(){
    n=rd(),st=rd();int x,y;
    for(int i=1;i<=n;i++) val[i]=rd();
    for(int i=1;i<n;i++){
        x=rd(),y=rd();
        add(x,y),add(y,x);
    }
    dfs(1,0);    
    for(int i=0;i<n;i++) if(dp[1][i]>=0) {
        printf("%d",i);break;    
    }
    return 0;
}

View Code