非常经典的树形DP(假设不会树形DP建议先看下面..我就是先看了别的题,,握手的什么的)
给一棵树,留下N条边(它若留下边父亲的边比留下),,问最后苹果最多多少个.......
建树我认为非常费劲,,,毕竟不太会........DP比較好理解吧,,,,,,,就是多想一想把,,,,,当作模板题记录下来~~~~
#include <iostream>
#include <cstdio> #include <bits/stdc++.h> using namespace std; const int maxn=101,maxq=100; int n;//jieidanshu int q;//baoliudebian int g[maxn][maxn];//juzhenbiaoshiliangdianguanxi int son[maxn][2]; //zijiedian int apple[maxn]; //jiluzijieidanshang de pingguoshu int dp[maxn][maxn]; //jiyihua int flag[maxn]; //biaoji int isleaf[maxn]; //jilushifouziye void create(int root) { int i,ct=0; for(i=1;i<=n;i++) { if(g[root][i]!=-1&&flag[i]==0) //zhaodaoleziye { son[root][ct++] = i; //diyigehuozhediergeziye apple[i]=g[root][i]; flag[i] = 1; create(i); //jixujianshu } } if(ct==0)//meiyouziye { isleaf[root]=1; } } int treedp(int root, int num) //num biaoshi shengxiade dianshu { if(num==0) return 0; //bushengxia if(isleaf[root]==1) return apple[root]; //zuihouyihang if(dp[root][num]!=-1) return dp[root][num]; //jiyihua int i,temp=0; for(i=0;i<num;i++) { temp=max(temp,treedp(son[root][0],i)+treedp(son[root][1],num-1-i)); } dp[root][num]=temp+apple[root]; //printf("%d**\n",dp[root][num]); return dp[root][num]; } int main() { int i,x,y,w; memset(g,-1,sizeof(g)); scanf("%d%d",&n,&q); for(i=1;i<=n-1;i++) { scanf("%d%d%d",&x,&y,&w); g[x][y]=w;//zhelihenzhongyaodexiangfa! g[y][x]=w; } memset(flag,0,sizeof(flag)); memset(isleaf,0,sizeof(isleaf)); flag[1]=1;// 1 shi morende apple[1]=0; create(1); memset(dp,-1,sizeof(dp)); printf("%d\n",treedp(1,q+1)); return 0; }