首页 > 其他 > 详细

HDU 1561The more, The Better(树形DP)

时间:2014-08-03 15:09:55      阅读:227      评论:0      收藏:0      [点我收藏+]

HDU 1561  The more, The Better

题目大意就不说了

直接DP[i][j]表示i为跟节点的子树上攻克j个城堡的所能获得的最多宝物的数量

DP[fa][j] = MAX{DP[fa][i-k] + DP[child][k]};

首先一个问题就是说如果子树u下的任意子节点被选择了,那么u是一定需要选择的,怎么在DP时保证准确性,其实这个很好解决,我们在计算时是需要枚举k(子节点的攻克数量)的,那么我们迫使k<j就可以了,这样的话DP[fa][j] 就不会被子节点的DP[child][j]更新掉保证了他的父节点一定在被选择的里面

另外一个问题就是如果枚举j时是从小到达枚举,那么DP[fa][j]很可能已经被当前的child更新过了,那么在计算DP[fa][j+1]或者以后时,很可能有会被放入同一个child,导致当前的child被选择了多次,所以我们需要逆序枚举j(k的顺序无关紧要了)

最后的结果就是个棵树上同样取DP值,只是一颗完整的树上可以一个也不取了

 1 #include <map>
 2 #include <set>
 3 #include <stack>
 4 #include <queue>
 5 #include <cmath>
 6 #include <ctime>
 7 #include <vector>
 8 #include <cstdio>
 9 #include <cctype>
10 #include <cstring>
11 #include <cstdlib>
12 #include <iostream>
13 #include <algorithm>
14 using namespace std;
15 #define INF ((LL)100000000000000000)
16 #define inf (-((LL)1<<40))
17 #define lson k<<1, L, mid
18 #define rson k<<1|1, mid+1, R
19 #define mem0(a) memset(a,0,sizeof(a))
20 #define mem1(a) memset(a,-1,sizeof(a))
21 #define mem(a, b) memset(a, b, sizeof(a))
22 #define FOPENIN(IN) freopen(IN, "r", stdin)
23 #define FOPENOUT(OUT) freopen(OUT, "w", stdout)
24 template<class T> T CMP_MIN(T a, T b) { return a < b; }
25 template<class T> T CMP_MAX(T a, T b) { return a > b; }
26 template<class T> T MAX(T a, T b) { return a > b ? a : b; }
27 template<class T> T MIN(T a, T b) { return a < b ? a : b; }
28 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }
29 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }
30 
31 //typedef __int64 LL;
32 typedef long long LL;
33 const int MAXN = 255;
34 const int MAXM = 110000;
35 const double eps = 1e-12;
36 int dx[4] = {-1, 0, 0, 1};
37 int dy[4] = {0, -1, 1, 0};
38 
39 int N, M;
40 int G[MAXN][MAXN], vis[MAXN], num[MAXN];
41 int DP[MAXN][MAXN], D[MAXN];
42 
43 void DFS(int u)
44 {
45     vis[u] = 1;
46     DP[u][1] = num[u];
47     for(int i=1;i<=N;i++)  if(G[u][i])
48     {
49         if(!vis[i]) DFS(i);
50         for(int j=M;j>0;j--)//这里为了保证是先从父节点更新,需要逆序
51             for(int k=0;k<j;k++)//k<j保证父节点不会被更新掉
52                 DP[u][j] = MAX(DP[u][j], DP[u][j-k] + DP[i][k]);
53     }
54 }
55 
56 int main()
57 {
58     //FOPENIN("in.txt");
59     while(~scanf("%d %d", &N, &M) &&( N||M))
60     {
61         int a;mem0(G);mem0(D);mem0(vis);mem0(DP);
62         for(int i=1;i<=N;i++) {
63             scanf("%d %d", &a, &num[i]);
64             if(a != 0)G[a][i] = 1;
65             else D[i] = 1;
66         }
67         for(int i=1;i<=N;i++) if(!vis[i]){
68             DFS(i);
69             if(D[i]) for(int j=M;j>=0;j--)//同样需要逆序,可以取到0
70             {
71                 for(int k=0;k<=j;k++)
72                     DP[0][j] = MAX(DP[0][j], DP[0][j-k] + DP[i][k]);
73             }
74         }
75         printf("%d\n", DP[0][M]);
76 
77     }
78     return 0;
79 }

 

HDU 1561The more, The Better(树形DP),布布扣,bubuko.com

HDU 1561The more, The Better(树形DP)

原文:http://www.cnblogs.com/gj-Acit/p/3888358.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!