讨论 / 处理成二叉树,记得记录右节点的值
2275689493 2017-03-11 00:07:50
点我顶贴 收藏 删除
//RQNOJ AC

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=2005;

int a,b;

int n,m,visit[maxn],dp[maxn][105];//第i个节点第j个人

struct node

{

int left,right,data;

} tree[maxn];

void sca_pre()

{

scanf("%d%d",&n,&m);

for(int i=1;i<=n;i++)

{

scanf("%d",&tree[i].data);

// if(tree[i].data<0) tree[i].data=0;

}

for(int i=1;i<=n;i++)

{

scanf("%d%d",&a,&b);

if(visit[a]==0) tree[a].left=b;

else tree[visit[a]].right=b;

visit[a]=b;

}

}

void work_dfs(int x,int k)

{

int maxx=0;

if(x<=0||k<=0) return;

if(dp[x][k]>0) return;

work_dfs(tree[x].right,k);

maxx=dp[tree[x].right][k];

for(int i=0;i<=k-1;i++)

{

work_dfs(tree[x].left,i);

work_dfs(tree[x].right,k-i-1);

maxx=max(maxx,dp[tree[x].left][i]+dp[tree[x].right][k-i-1]+tree[x].data);

}

dp[x][k]=maxx;

}

int main()

{

sca_pre();

work_dfs(tree[0].left,m);

printf("%d\n",dp[tree[0].left][m]);

// printf("%d %d %d\n",tree[0].left,tree[0].right,tree[0].data);

return 0;

}

查看更多回复
提交回复