HDU 1011 树形背包(DP) Starship Troopers

题目链接: HDU 1011 树形背包(DP) Starship Troopers

题意: 地图中有一些房间, 每个房间有一定的bugs和得到brains的可能性值, 一个人带领m支军队从入口(房间1)进入,

只有到达某个房间并且将bugs全部杀死, 才能得到相应该的值. 问最多能获得多少可能性值.

PS 1). 一支军队能杀死 20 bugs, 当一支军队发生战争之后就不能再到其它地方去了

2) . 不能走回头路

分析: [树形背包] 用dp[i][j]表示到达房间 i 的军队数为 j 时, 在房间 i 及与它相连那些房间中共获得的值.

dp[j][k] = max( dp[j][k], dp[j][k-t]+dp[jv][t] ) (其中 jv 是与 j 相邻的房间)

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf = 0x7FFFFFFF;
const int maxn = 111;

struct node{
    int v;
    node *next;
}tree[maxn<<1], *head[maxn];

int ptr,n;
int dp[105][2005], bug[105], w[105];
bool vis[105];

void Init(){
    ptr=1;
    memset(head,0,sizeof(head));
    memset(dp,0,sizeof(dp));
    memset(vis,false,sizeof(vis));
}

void AddEdge(int a,int b){
    tree[ptr].v=b;
    tree[ptr].next=head[a];
    head[a]=&tree[ptr++];
}

int DFS(int cnt,int M){
    if(M==0) return 0;
    int m=M-bug[cnt];
    vis[cnt]=true;
    node *p=head[cnt];
    int Max=0;
    while(p!=NULL){
        if(vis[p->v]){
            p = p->next; continue;
        }
        for(int i=m;i>=bug[p->v];--i)
            dp[p->v][i] = DFS(p->v,i);
        for(int i=m;i>=bug[p->v];--i)
            for(int j=i;j>=bug[p->v];--j)
                dp[cnt][i]=max(dp[cnt][i],dp[cnt][i-j]+dp[p->v][j]);
        p=p->next;
    }
    return w[cnt]+dp[cnt][m];
}

int main(){
    int m;
    while(~scanf("%d%d",&n,&m)&&!(n==-1&&m==-1)){
        Init();
        for(int i=1;i<=n;++i){
            int a; scanf("%d%d",&a, w+i);
            bug[i]=(a%20)?1:0;
            bug[i]+=a/20;
        }
        for(int i=1;i<n;++i){
            int a,b; scanf("%d%d",&a,&b);
            AddEdge(a,b);
            AddEdge(b,a);
        }
        if(m<bug[1]){
            puts("0"); continue;
        }
        printf("%d
", DFS(1,m) );
    }
    return 0;
}


.