首页 > 代码库 > HDU 1561The more, The Better（树形DP）

HDU 1561The more, The Better（树形DP）

2024-07-15 13:11:00   227人阅读

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, mid18 #define rson k<<1|1, mid+1, R19 #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--)//同样需要逆序，可以取到070             {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 }

 


联系
我们