https://www.luogu.com.cn/problemnew/solution/P2015
解法1:记忆化搜索
1 #include <iostream> 2 #include <cstring> 3 #include <vector> 4 #define MAX(a,b) (a>b?a:b) 5 #define Maxsize 100+1 6 using namespace std; 7 struct node{ 8 int id; 9 int val; 10 node(int a,int b){ 11 id = a;val = b; 12 } 13 }; 14 int dp[Maxsize][Maxsize]; // 以第i个顶点作为根节点,保留至多j个枝条，所能得到的最大答案 15 bool vis[Maxsize]; 16 vector<node> tree[Maxsize]; 17 vector<node> temp[Maxsize]; 18 void build_tree(int x){ 19 vis[x] = true; 20 for (auto it = temp[x].begin(); it != temp[x].end(); it++) { 21 if(!vis[it->id]){ 22 tree[x].push_back(*it); 23 build_tree(it->id); 24 } 25 } 26 } 27 int fun(int x,int num){ // 以第i个顶点作为根节点,保留至多j个枝条，所能得到的最大答案 28 if (dp[x][num] != -1) { 29 return dp[x][num]; 30 }else if(tree[x].empty() || num == 0){ 31 return 0; 32 }else{ 33 int p1 = MAX(fun(tree[x][0].id,num-1)+tree[x][0].val,fun(tree[x][1].id,num-1)+tree[x][1].val); // 二选一 34 int p2 = 0; 35 for (int i = 1; i <= num - 1; i++) { 36 int j = num - i; 37 int temp = fun(tree[x][0].id,i-1) + tree[x][0].val + fun(tree[x][1].id,j-1) + tree[x][1].val; 38 p2 = MAX(p2,temp); 39 } 40 return dp[x][num] = MAX(p1,p2); 41 } 42 } 43 int main(){ 44 int n,q; 45 int a,b,c; 46 cin >> n >> q; 47 for (int i = 1; i < n; i++) { 48 cin >> a >> b >> c; 49 temp[a].push_back(node(b,c)); 50 temp[b].push_back(node(a,c)); 51 } 52 memset(dp,-1,sizeof(dp)); 53 build_tree(1); 54 cout << fun(1,q); 55 return 0; 56 }
解法2:树上DP
由于数据结构是一棵树，导致我们不能用常规的方式去DP。这是因为，由状态转移方程可知，每一个子问题都要用到当前根节点的子孙的结果。因此，我们需要依靠dfs，先解决子问题，再回溯求解原问题。
注意，dfs仅仅只是我们到达子问题的手段，而求解问题的核心方式还是DP。它与记忆化搜索都用到了dfs，但有着很大的区别。
1 #include <iostream> 2 #include <vector> 3 #define MAX(a,b) (a>b?a:b) 4 #define Maxsize 100+1 5 using namespace std; 6 int n,q; 7 int dp[Maxsize][Maxsize]; 8 struct node{ 9 int id; 10 int val; 11 node(int a,int b){ 12 id = a; val = b; 13 } 14 }; 15 bool vis[Maxsize]; 16 vector<node> tree[Maxsize]; 17 void dfs(int x){ 18 vis[x] = true; 19 for (auto it = tree[x].begin(); it != tree[x].end(); it++) { 20 if(!vis[it->id]){ 21 vis[it->id] = true; 22 dfs(it->id); 23 vis[it->id] = false; 24 } 25 } 26 if(tree[x].size()==1){ 27 return; 28 }else{ 29 vector<int> m; 30 vector<int> v; 31 for (auto it = tree[x].begin(); it != tree[x].end(); it++) { 32 if(!vis[it->id]){ 33 m.push_back(it->id); 34 v.push_back(it->val); 35 } 36 } 37 for (int i = 1; i <= q; i++) { // 至少也有一个出边 , 一个也没用的话,答案不用算肯定是0 38 int p1 = MAX(dp[m[0]][i-1]+v[0],dp[m[1]][i-1]+v[1]); 39 for (int j = 1; i-j >= 1; j++) { 40 dp[x][i] = MAX(dp[x][i],dp[m[0]][j-1]+v[0]+dp[m[1]][i-j-1]+v[1]); 41 } 42 dp[x][i] = MAX(dp[x][i],p1); 43 } 44 } 45 } 46 int main(){ 47 int a,b,c; 48 cin >> n >> q; 49 for (int i = 1; i < n; i++) { 50 cin >> a >> b >> c; 51 tree[a].push_back(node(b,c)); 52 tree[b].push_back(node(a,c)); 53 } 54 dfs(1); 55 cout << dp[1][q]; 56 return 0; 57 }