首页 > ACM题库 > HDU-杭电 > HDU 4169-Wealthy Family-动态规划-[解题报告]HOJ
2015
05-23

HDU 4169-Wealthy Family-动态规划-[解题报告]HOJ

Wealthy Family

问题描述 :

While studying the history of royal families, you want to know how wealthy each family is. While you have various ‘net worth’ figures for each individual throughout history, this is complicated by double counting caused by inheritance. One way to estimate the wealth of a family is to sum up the net worth of a set of k people such that no one in the set is an ancestor of another in the set. The wealth of the family is the maximum sum achievable over all such sets of k people. Since historical records contain only the net worth of male family members, the family tree is a simple tree in which every male has exactly one father and a non-negative number of sons. You may assume that there is one person who is an ancestor of all other family members.

输入:

The input consists of a number of cases. Each case starts with a line containing two integers separated by a space: N (1 <= N <= 150,000), the number of people in the family, and k (1 <= k <= 300), the size of the set. The next N lines contain two non-negative integers separated by a space: the parent number and the net worth of person i (1 <= i <= N). Each person is identified by a number between 1 and N, inclusive. There is exactly one person who has no parent in the historical records, and this will be indicated with a parent number of 0. The net worths are given in millions and each family member has a net worth of at least 1 million and at most 1 billion.

输出:

The input consists of a number of cases. Each case starts with a line containing two integers separated by a space: N (1 <= N <= 150,000), the number of people in the family, and k (1 <= k <= 300), the size of the set. The next N lines contain two non-negative integers separated by a space: the parent number and the net worth of person i (1 <= i <= N). Each person is identified by a number between 1 and N, inclusive. There is exactly one person who has no parent in the historical records, and this will be indicated with a parent number of 0. The net worths are given in millions and each family member has a net worth of at least 1 million and at most 1 billion.

样例输入:

5 3
0 10
1 15
1 25
1 35
4 45
3 3
0 10
1 10
2 10

样例输出:

85
impossible

hdu 4169

题意:给定一棵树,每一节点都有一权值,要求选出总权值最大的K个点,同时这K个点中任意一个点都不能是其他节点的祖先。

节点数太多了,150000 ,爆内存的,所以开了一个临时数组保存

注意优化 子分支的状态数 复杂度O(n*k^2)

 

 #include<iostream>
 #include<cstring>
 #include <cstdio>
 #include<string>
 #include<queue>
 #include<vector>
 #include<map>
 #include <set>
 #include<ctime>
 #include<cmath>
 #include <cstdlib>
 #include<algorithm>
 #include <climits>
 using namespace std;
 
 #define LL long long 
 #define nMAX 150001
 #define mMAX 301
 int dp[mMAX];
 int w[nMAX],start[nMAX];
 int n,m,p;
 vector<int> G[nMAX];
 int dfs(int u,int *dp){
     int best[mMAX]; fill(best,best+m+1,0); 
     int t=0;
     for(int i=0;i<G[u].size();i++){
         int v=G[u][i];
         fill(dp,dp+m+1,0);
         int now=dfs(v,dp); 
         for(int j=t;j>=0;j--) 
             for(int k=1;k<=now&&j+k<=m;k++)
                 if((dp[k]&&best[j]) 
                     ||(!j&&dp[k]))
                     best[j+k]=max(best[j+k],best[j]+dp[k]);
         t+=now;
     }
     dp[1]=max(w[u],best[1]); 
     for(int i=2;i<=m;i++) dp[i]=best[i];
     if(!G[u].size()) t++; 
     return t;
 }
 int main(){
     while(scanf("%d%d",&n,&m)!=EOF){
         int root;
         p=0;
         for(int i=1;i<=n;i++) G[i].clear();
         for(int i=1;i<=n;i++){
             int u;
             scanf("%d%d",&u,&w[i]);
             if(u==0) root=i;
             else  G[u].push_back(i);
         }
         dfs(root,dp);
         int ans=dp[m];
         if(ans) printf("%d\n",ans);
         else printf("impossible\n");
     }
 }


以上参考 http://www.cnblogs.com/nanke/archive/2012/03/04/2379261.html

另一种优化 :复杂度 O(n*k)

 #include<iostream>
 #include<cstring>
 #include <cstdio>
 #include<string>
 #include<queue>
 #include<vector>
 #include<map>
 #include <set>
 #include<ctime>
 #include<cmath>
 #include <cstdlib>
 #include<algorithm>
 #include <climits>
 using namespace std;
 
 #define LL long long 
 #define nMAX 150001
 #define mMAX 301
 int dp[mMAX];
 int w[nMAX],start[nMAX];
 int n,m,p;
 vector<int> G[nMAX];
 void dfs(int u,int *dp){
     int best[mMAX];
     copy(dp,dp+m+1,best);
     for(int i=0;i<G[u].size();i++){
         int v=G[u][i];
         dfs(v,best); 
     }
     for(int i=m;i>=1;i--){
         if( (dp[i-1]||!(i-1) )&&
             dp[i-1]+w[u]>best[i]) dp[i]=dp[i-1]+w[u];
         else dp[i]=best[i];
     }
 }
 int main(){
     while(scanf("%d%d",&n,&m)!=EOF){
         int root;
         p=0;
         for(int i=1;i<=n;i++) G[i].clear();
         for(int i=1;i<=n;i++){
             int u;
             scanf("%d%d",&u,&w[i]);
             if(u==0) root=i;
             else  G[u].push_back(i);
         }
         fill(dp,dp+m+1,0);
         dfs(root,dp);
         int ans=dp[m];
         if(ans) printf("%d\n",ans);
         else printf("impossible\n");
     }
 }

 

 

参考:http://www.cnblogs.com/louisnit/archive/2012/03/27/2420284.html