HDU 1011 트리 백팩(DP) Starship Troopers

제목 링크: HDU 1011 트리 백팩(DP) Starship Troopers
제목: 지도에 몇 개의 방이 있는데 각 방마다 일정한 버그가 있고 브레인스를 받을 가능성치가 있다. 한 사람이 m지군을 이끌고 입구(방1)로 들어간다.
어떤 방에 도착해서 버그를 모두 죽여야만 상응하는 값을 얻을 수 있다.최대 가능성치를 얼마나 얻을 수 있느냐고 물었다.
          PS  1). 한 군대는 20bugs를 죽일 수 있지만, 한 군대가 전쟁을 일으킨 후에는 다시는 다른 곳으로 갈 수 없다
                 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;

}





.