Tree_DP。
要注意到樹枝上的蘋果個數有可能是0個，所以一開始構圖的時候不能用g[i][j]==0表示結點i和j之間沒有邊。
以下是我的代碼：
#include<iostream>
#include<string.h>
#define maxn 107
#define max(a,b) (a>b?a:b)
using namespace std;
struct
{
long l,r;
}tree[maxn];
long n,m,g[maxn][maxn],d[maxn][maxn];
bool used[maxn];
void build_tree(long node)
{
bool first=true;
used[node]=true;
for(long i=1;i<=n;i++)
if(!used[i]&&g[node][i]!=-1)
{
if(first)
{
tree[node].l=i;
first=false;
}
else
tree[node].r=i;
build_tree(i);
}
}
long dp(long i,long j)
{
if(d[i][j]!=-1) return d[i][j];
d[i][j]=0;
d[i][j]=max(dp(tree[i].l,j-1)+g[i][tree[i].l],dp(tree[i].r,j-1)+g[i][tree[i].r]);
for(long k=0;j-k-2>=0;k++)
d[i][j]=max(d[i][j],dp(tree[i].l,k)+dp(tree[i].r,j-k-2)+g[i][tree[i].l]+g[i][tree[i].r]);
return d[i][j];
}
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
cin>>n>>m;
memset(g,-1,sizeof(g));
for(long i=1;i<=n-1;i++)
{
long a,b,w;
cin>>a>>b>>w;
g[a][b]=g[b][a]=w;
}
// Input
memset(tree,0,sizeof(tree));
memset(used,false,sizeof(used));
build_tree(1);
// Build Tree
/*
for(long i=1;i<=n;i++)
cout<<tree[i].l<<" "<<tree[i].r<<endl;
//*/
for(long i=0;i<=n;i++)
for(long j=0;j<=n;j++)
d[i][j]=-1;
for(long i=0;i<=n;i++)
d[0][i]=d[i][0]=0;
// Init
cout<<dp(1,m)<<endl;
// Dp & Output
return 0;
}
posted on 2010-09-12 13:19
lee1r 閱讀(251)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：動態規劃