Hdu 1011 Starship Troopers (DP 나무형 DP (배낭))

제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=1011
제목: 나무 한 그루 에 n 개의 정점 이 있 고 n - 1 개의 가장자리 가 있 습 니 다. 꼭대기 마다 bugs 가 있 습 니 다. 지금 폭탄 (폭탄 으로 하 세 요) 으로 폭격 해 야 합 니 다. 폭탄 하나 에 최대 20 마리 의 bug 가 폭사 합 니 다. 만약 에 어 딘 가 에 0 마리 의 bug 가 있다 면 다음 노드 로 굴 러 가서 폭격 할 수 있 습 니 다. n < = 100, 변 m < = 100
문제 풀이 방향: 비교적 간단 한 트 리 DP + 가방.본 문제 의 의존 관 계 는 나무 가장자리 로 이해 할 수 있다. 서브 노드 에 도착 하려 면 반드시 부모 노드 를 거 쳐 야 한다. 본질 은 똑 같다. 나 무 를 만 들 면 dp 를 어떻게 진행 하 는 지, 문제 풀이 의 핵심 은 서브 노드 에서 정 보 를 어떻게 얻 는 지 하 는 것 이다.
    하나의 키 노드 는 m 개의 상 태 를 되 돌 릴 수 있 고 모든 상 태 는 용량 이 j 임 을 나타 낸다.(j < = m) 시 가장 많이 튀 긴 bug, 한 노드 중 한 상태 만 선택 하여 이동 할 수 있 습 니 다. 각 노드 에 몇 개의 키 노드 가 있 으 면 문 제 는 그룹 가방 으로 바 꿉 니 다. 몇 개의 하위 노드 는 몇 개의 그룹 가방 입 니 다. 부 피 는 몇 개의 장 소 를 선택 하고 가 치 는 Boos 의 가능성 입 니 다. 본 문 제 는 m 를 0 으로 특별히 판단 할 때 직접 출력 0 입 니 다.
     상태 전이 방정식: dp [v] [1] = bug [v]; (v 는 잎 노드)
                          dp [v] [j] = max (dp [v] [j], dp [v] [j - i] + dp [k] [i]); (v 는 비 잎 노드 이 고 j 는 사용자 개 수 를 나타 내 며 i 는 용량 이 고 k 는 v 의 하위 노드 이다.)     알고리즘 복잡 도 O (sum (num [i], num [s]) (num [i] 는 특정한 노드 의 잎 자손 개수, num [s] 는 i 의 자식 노드 의 잎 자손 개수)
테스트 데이터:
5 10 50 10 40 10 40 20 65 30 70 30 1 2 1 3 2 4 2 5 1 1 20 7 5 0 50 10 40 10 40 20 65 30 70 30 1 2 1 3 2 4 2 5 4 1 0 10 0 10 0 10 0 10 1 2 2 3 1 4 -1 -1
코드:

#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
#define MAX 110
#define max(a,b) (a)>(b)?(a):(b)


int val[MAX],need[MAX];
vector<int> tree[MAX];
int cnt,n,m,dp[MAX][MAX],vis[MAX];


void Tree_DP(int s){

    if (vis[s]) return ;
    vis[s] = 1;
	int i,j,k,tp,temp;


    for (i = need[s]; i <= m; ++i) 
		dp[s][i] = val[s];
    for (i = 0; i < tree[s].size(); ++i) {

        tp = tree[s][i];
        if (vis[tp]) continue;
        Tree_DP(tp);
        

        for (j = m; j >= need[s]; --j)
            for (k = 1; k + j <= m; ++k)
                if (dp[tp][k]) {

		            temp = dp[s][j] + dp[tp][k];
                    dp[s][j+k] = max(dp[s][j+k],temp);
                }
    }
}


int main()
{
    int i,j,k,a,b;


    while (scanf("%d%d",&n,&m),n + m != -2){
    
        for (i = 1; i <= n; ++i){

            scanf("%d%d",&need[i],&val[i]);
			tree[i].clear();
            need[i] = (need[i] + 19) / 20;
        }

            
        for (i = 1; i < n; ++i){

            scanf("%d%d",&a,&b);
			if (a < b)
            tree[a].push_back(b);
            else 
			tree[b].push_back(a);
        }
		

		if (m == 0) {

			printf("0
");
			continue;
		}

        memset(dp,0,sizeof(dp));
        memset(vis,0,sizeof(vis));
        Tree_DP(1);
        printf("%d
",dp[1][m]);
    }
    return 0;
}

이 글 은 ZeroClock 오리지널 이지 만 우 리 는 형제 이기 때문에 옮 길 수 있 습 니 다.