首页 > 代码库 > 动态规划 树型DP
动态规划 树型DP
codves5565 二叉苹果树
有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。
给定需要保留的树枝数量，求出最多能留住多少苹果。
第1行2个数，N和Q(1<=Q<= N,1<N<=100)。
N表示树的结点数，Q表示要保留的树枝数量。接下来N-1行描述树枝的信息。
每行3个整数，前两个是它连接的结点的编号。第3个数是这根树枝上苹果的数量。
每根树枝上的苹果不超过30000个。
剩余苹果的最大数量。
5 2
1 3 1
1 4 10
2 3 20
3 5 20
21
对于20%数据 n<=20;
对于100%数据1<N<=100,1<=Q<= N.
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; struct node { int l,r,c; }map[2001]; int f[1005][1005]; int n,q,maxx=0; void dfs(int i,int j) { int k; if(j==0) f[i][j]=0; else if(map[i].r==0&&map[i].l==0) f[i][j]=map[i].c; else { f[i][j]=0; for(k=0;k<j;k++) { if(f[map[i].l][k]==0) dfs(map[i].l,k); if(f[map[i].r][j-k-1]==0) dfs(map[i].r,j-k-1); f[i][j]=max(f[i][j],f[map[i].l][k]+f[map[i].r][j-k-1]+map[i].c); // maxx=max(maxx,f[i][j]); //printf("%d ",maxx); } } } int main() { scanf("%d %d",&n,&q); int v,u,c; for(int i=1;i<n;i++) { int p=0; scanf("%d %d %d",&v,&u,&c); for(int j=1;j<=n;j++) if(map[j].l==u||map[j].r==u) p=1; if(p==0) { if(map[v].l==0) map[v].l=u; else if(map[v].r==0) map[v].r=u; map[u].c=c; } else { if(map[u].l==0) map[u].l=v; else if(map[u].r==0) map[u].r=v; map[v].c=c; } } //for(int i=1;i<=n;i++) printf("%d %d %d\n",map[i].l,map[i].r,map[i].c); dfs(1,q+1); //for(int i=1;i<=n;i++) printf("%d ",map[i]); printf("%d",f[1][q+1]); }
初始化：f[i][0]=0,f[i][1]=map[i];
转移方程:f[i][j]=max(f[i][j],f[map[i].l][k]+f[map[i].r][j-k-1]+map[i].c);
谢谢姚老教导;
接下来膜ccz大爷 附代码 很强势;
#include<bits/stdc++.h> struct edge{ int to,v; }; int n,q; std::vector<edge>e[107]; int f[107][107],sz[107],v[107]; void maxs(int&a,int b){if(a<b)a=b;} void f1(int w,int pa){ sz[w]=1; f[w][1]=v[w]; for(int i=0;i<e[w].size();++i){ int u=e[w][i].to; if(u==pa)continue; v[u]=e[w][i].v; f1(u,w); for(int k=sz[w];k>=1;--k) for(int j=1;j<=sz[u];++j){ maxs(f[w][k+j],f[w][k]+f[u][j]); } sz[w]+=sz[u]; } } int main(){ scanf("%d%d",&n,&q); for(int i=1,a,b,c;i<n;++i){ scanf("%d%d%d",&a,&b,&c); e[a].push_back((edge){b,c}); e[b].push_back((edge){a,c}); } f1(1,0); printf("%d\n",f[1][q+1]); return 0; }
------------------------
codves1380 没有上司的舞会
Ural大学有N个职员，编号为1~N。他们有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会，要求与会职员的快乐指数最大。但是，没有职员愿和直接上司一起与会。
第一行一个整数N。(1<=N<=6000)
接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128<=Ri<=127)
接下来N-1行，每行输入一对整数L,K。表示K是L的直接上司。
最后一行输入0,0。
输出最大的快乐指数。
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0
5
各个测试点1s
#include<cstdio> #include<algorithm> #include<cstring> #define long long ll using namespace std; const int N=6010; int map[N]; struct node { int to,next; }e[N*2]; int boss[N]={0}; int first[N],cnt=0; int is_boss; int f[N][5]; void insert(int v,int u) { e[++cnt].to=u;e[cnt].next=first[v];first[v]=cnt; //printf("===========\n%d %d %d\n==========\n",e[cnt].to,e[cnt].next,first[cnt]); } void dfs(int x) { f[x][0]=0;f[x][1]=map[x]; for(int i=first[x];i;i=e[i].next) { int p=e[i].to; dfs(p); f[x][0]+=max(f[p][0],f[p][1]); f[x][1]+=f[p][0]; //printf("%d %d\n",f[x][0],f[x][1]); } } int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&map[i]); int v,u; while(1) { scanf("%d %d",&v,&u); if(v+u==0) break; boss[v]++; insert(u,v); } //printf("-------------------------\n"); for(int i=1;i<=n;i++) if(!boss[i]) {is_boss=i;break;} //printf("%d \n",is_boss); dfs(is_boss); printf("%d",max(f[is_boss][1],f[is_boss][0])); return 0; }
转移方程:
f[]中的0代表不选，1代表选；
谢谢姚老教导(again);
-----------------------------------------
动态规划 树型DP