首页 > 代码库 > csu 2014 summer day 4 树形dp升阶
csu 2014 summer day 4 树形dp升阶
POJ 1155
题意：电视台发送信号给很多用户，每个用户有愿意出的钱，电视台经过的路线都有一定费用，求电视台不损失的情况下最多给多少用户发送信号。
要知道用户都在叶子节点，费用消耗在使用选择的路径上，每条路径的使用费用给出，每个用户支付的费用给出。
输入：N为总节点数，M为用户数，1为电视台, 2 to N-M 是中转站，N-M+1到N是潜在用户
对于1到N-M的中继点，给出连接的点的个数K，K对（A，C）表示连接到A点，这条路径的费用是C
最后是M个整数，表示用户支付的费用
分析：
int num[maxn];//记录每个节点下面的总用户数int dp[maxn][maxn];//i：i的子树中，j：节点下面的使用用户数，能达到的最大的剩余利润//dp：最大剩余利润：线路费用-使用用户支付的费用
相当于树形背包：
dp[u][j+k]=max(dp[u][j+k],temp[j]+dp[v][k]-len[u][i]);
temp[j]表示原来的dp[u][j]
对于搜索出来的一棵树，对于它的孩子，可以选择加还是不加，其中len[u][i]恰好表示u到当前选择的v的代价
完整写法：
for(int j=0;j<=num[u];j++){ temp[j]=dp[u][j]; } for(int j=0;j<=num[u];j++){ for(int k=1;k<=num[v];k++){//注意k!=0,否则多减少了i dp[u][j+k]=max(dp[u][j+k],temp[j]+dp[v][k]-len[u][i]); } } num[u]+=num[v];代码：
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <vector> 5 #define maxn 3100 6 #define INF 99999999 7 using namespace std; 8 9 int num[maxn];//记录每个节点下面的总用户数10 int dp[maxn][maxn];//i：处理的节点数，j：节点下面的使用用户数11 //dp：最大剩余利润：线路费用-使用用户支付的费用12 int N,M;13 vector<int>G[maxn];14 vector<int>len[maxn];15 int temp[maxn];16 void dfs(int u,int fa){17 18 // cout<<"u="<<u<<endl;19 // for(int i=0;i<G[u].size();i++){20 // int v=G[u][i];21 // if (v==fa) continue;22 // dfs(v);23 // num[u]+=num[v];24 // }25 // //用子节点更新u26 // int sum=0;27 // for(int i=0;i<G[u].size();i++){//依次枚举下层节点28 // int v=G[u][i];29 // if (v==fa) continue;30 // for(int j=0;j<=sum;j++){//设置这个的原因是，仔细看下面，原本的dp[u][j]已经被覆盖了31 // temp[j]=dp[u][j];32 // }33 // for(int j=0;j<=sum;j++){34 // for(int k=0;k<=num[v];k++){35 // dp[u][j+k]=max(dp[u][j+k],temp[j]+dp[v][k]-len[u][i]);36 // }37 // }38 // sum+=num[v];39 // }40 //我们可以看出，上面两部分可以和在一起写，而且每次更新的num[u]就是sum41 42 dp[u][0]=0;43 for(int i=0;i<G[u].size();i++){44 int v=G[u][i];45 if (v==fa) continue;46 dfs(v,u);47 for(int j=0;j<=num[u];j++){48 temp[j]=dp[u][j];49 }50 for(int j=0;j<=num[u];j++){51 for(int k=1;k<=num[v];k++){//注意k!=0,否则多减少了i52 dp[u][j+k]=max(dp[u][j+k],temp[j]+dp[v][k]-len[u][i]);53 }54 }55 num[u]+=num[v];56 }57 return ;58 }59 void solve(){60 for(int i=M;i>=0;i--){61 if (dp[1][i]>=0) {62 printf("%d\n",i);63 break;64 }65 }66 return ;67 }68 int main(){69 while(~scanf("%d%d",&N,&M)){70 for(int i=0;i<=N;i++) G[i].clear();71 for(int i=1;i<=N-M;i++){72 int k;73 scanf("%d",&k);74 for(int j=1;j<=k;j++){75 int v,c;76 scanf("%d%d",&v,&c);77 G[i].push_back(v);78 len[i].push_back(c);79 }80 }81 memset(num,0,sizeof(num));82 for(int i=0;i<=N;i++){83 for(int j=0;j<=N;j++) dp[i][j]=-INF;84 }85 for(int i=N-M+1;i<=N;i++){86 scanf("%d",&dp[i][1]);87 num[i]=1;88 }89 dfs(1,-1);90 solve();91 }92 return 0;93 }
POJ 2486
题意：Wshxzt从根节点1开始在苹果树上游历，树上的每个节点都会存在apple[i]个苹果，从一个节点到它的邻节点耗费步数1。现在Wshxzt可以步行step步，求她可以得到的最大苹果数量。
输入：N节点数，K最大步数，每个节点的苹果数，N-1条边
分析：
代码：
1 #include<iostream> 2 #include<stdio.h> 3 #include<string.h> 4 #include<vector> 5 #define MAXN 110 6 #define MAXK 220 7 using namespace std; 8 9 vector<int>G[MAXN];10 int anum[MAXN];11 int dp[MAXN][MAXK][2];12 int N,K;13 int temp[MAXN];14 void dfs(int u,int fa){15 dp[u][0][1]=anum[u];16 dp[u][0][0]=anum[u];17 for(int i=0;i<G[u].size();i++){18 int v=G[u][i];19 if (v==fa) {20 continue;21 }22 dfs(v,u);23 for(int j=K;j>=0;j--){24 for(int t=1;t<=j;t++){25 dp[u][j][0]=max(dp[u][j][0],dp[v][t-1][0]+dp[u][j-t][1]);26 if (t==1) continue;27 dp[u][j][0]=max(dp[u][j][0],dp[v][t-2][1]+dp[u][j-t][0]);28 dp[u][j][1]=max(dp[u][j][1],dp[v][t-2][1]+dp[u][j-t][1]);29 }30 }31 }32 33 return ;34 }35 int main(){36 while(~scanf("%d%d",&N,&K)){37 for(int i=1;i<=N;i++){38 scanf("%d",&anum[i]);39 }40 for(int i=0;i<=N;i++) G[i].clear();41 for(int i=1;i<=N-1;i++){42 int u,v;43 scanf("%d%d",&u,&v);44 G[u].push_back(v);45 G[v].push_back(u);46 }47 memset(dp,0,sizeof(dp));48 for(int i=0;i<=N;i++){49 for(int j=0;j<=K;j++) dp[i][j][0]=dp[i][j][1]=anum[i];50 }51 dfs(1,-1);52 printf("%d\n",dp[1][K][0]);53 }54 return 0;55 }
POJ 1947
POJ 1848
POJ 1655
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。