hdu 1561 The more, The Better----树形dp+有依赖的背包
发布时间:2020-12-13 19:45:01 所属栏目:百科 来源:网络整理
导读:0为根节点 dp[0][m+1]表示 从0节点开始覆盖,覆盖m+1个点的最大值 #includestdio.h#includestring.h#includevector#includealgorithmusing namespace std;int dp[220][220],v[220];vectorint q[220];void dfs(int p,int M){int len=q[p].size();dp[p][1]=v[p
0为根节点 dp[0][m+1]表示 从0节点开始覆盖,覆盖m+1个点的最大值
#include<stdio.h> #include<string.h> #include<vector> #include<algorithm> using namespace std; int dp[220][220],v[220]; vector<int> q[220]; void dfs(int p,int M) { int len=q[p].size(); dp[p][1]=v[p]; for(int i=0;i<len;i++){ //分组背包,len组 if(M>1) dfs(q[p][i],M-1); //递归 for(int j=M;j>=1;j--) for(int k=1;k<j;k++) dp[p][j]=max(dp[p][j],dp[p][j-k]+dp[q[p][i]][k]); } } int main() { int n,m; int i,j,k; while(scanf("%d%d",&n,&m),n||m){ for(i=0;i<=n;i++) q[i].clear(); memset(dp,sizeof(dp)); for(i=1;i<=n;i++){ scanf("%d%d",&k,&v[i]); q[k].push_back(i); } v[0]=0; dfs(0,m+1); // dfs(节点,此节点一下的将要覆盖的点) 因为算了0节点,所以m+1 printf("%dn",dp[0][m+1]); } } *************** 好像 树形dp能用二维写。。 http://www.52php.cn/article/p-msnhrvnr-xx.html 这题就是二维优化的, 然后用同样的方法优化了下,这题。。 上面的代码125ms 下面的代码15ms #include<stdio.h> #include<string.h> #include<vector> #include<algorithm> using namespace std; int dp[220][220],v[220]; vector<int> q[220]; int flag[220]; void dfs(int p,int M) { int i,k,u; int len=q[p].size(); for(i=0;i<len;i++) { u=q[p][i]; if(flag[u]) { for(j=M-1;j>=0;j--) dp[u][j]=dp[p][j]; if(M-1>=0) dfs(u,M-1); for(j=M;j>=1;j--) dp[p][j]=max(dp[p][j],dp[u][j-1]+v[u]); } else { for(j=M;j>=1;j--) dp[p][j]=max(dp[p][j],dp[p][j-1]+v[u]); } } } int main() { int n,m; int i,k; while(scanf("%d%d",n||m){ for(i=0;i<=n;i++) q[i].clear(); memset(flag,sizeof(flag)); memset(dp,sizeof(dp)); for(i=1;i<=n;i++){ scanf("%d%d",&v[i]); q[k].push_back(i); flag[k]=1; } v[0]=0; dfs(0,m); printf("%dn",dp[0][m]); } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |