Posted on 2011-11-23 14:56
C小加 閱讀(1414)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
解題報(bào)告
題意：一棵二叉蘋(píng)果樹(shù)，每個(gè)樹(shù)枝上都有蘋(píng)果，求剪枝后剩下Q根樹(shù)枝的時(shí)候的最大蘋(píng)果數(shù)量。（剪枝的時(shí)候不能連根拔起）
思路：TreeDP。先由題給出的關(guān)系建立一棵二叉樹(shù)，把邊上的蘋(píng)果移動(dòng)到子結(jié)點(diǎn)，然后對(duì)樹(shù)進(jìn)行自底而上的DP，狀態(tài)轉(zhuǎn)移方程式為：f[root][j]=max(f[root.lc][i]+f[root][j-1-i])+val[root];意思就是說(shuō)當(dāng)根root要保留j個(gè)點(diǎn)=root的左孩子保留i個(gè)點(diǎn)的最大蘋(píng)果數(shù)+root的右孩子保留j-1-i個(gè)點(diǎn)的最大蘋(píng)果數(shù)+root點(diǎn)的蘋(píng)果數(shù)。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=103;
typedef struct
{
int lc,rc;
int val;
}Node;
Node tree[MAXN];
int m,n;
int arr[MAXN][MAXN];
int f[MAXN][MAXN];
int vis[MAXN];
void Create(int root)
{
vis[root]=1;
for(int i=1;i<=m;i++)
{
if(!vis[i]&&arr[root][i])
{
if(!tree[root].lc)
tree[root].lc=i;
else tree[root].rc=i;
tree[i].val=arr[root][i];
Create(i);
}
}
}
int TreeDP(int root,int e)
{
if(!root||!e)return 0;
if(f[root][e])retu rn f[root][e];
int maxx=0;
int l,r;
for(int i=0;i<e;i++)
{
l=TreeDP(tree[root].lc,i);
r=TreeDP(tree[root].rc,e-i-1);
maxx=max(l+r,maxx);
}
f[root][e]=maxx+tree[root].val;
return f[root][e];
}
int main()
{
memset(arr,0,sizeof(arr));
memset(vis,0,sizeof(vis));
memset(tree,0,sizeof(tree));
scanf("%d %d",&m,&n);
int l,f,v;
for(int i=1;i<m;i++)
{
scanf("%d %d %d",&l,&f,&v);
arr[l][f]=arr[f][l]=v;
}
Create(1);
printf("%d\n",TreeDP(1,++n));
return 0;
}