我是靠谱客的博主 霸气火,最近开发中收集的这篇文章主要介绍Apple Tree POJ - 2486(三维 树形背包)思路,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

思路

首先可以想到dp[i][j]表示在i节点可以走j步获得的最大值,其实就是类似于将j步分给它的子节点,树上背包问题。
但是这题还有一个要点,那就是当你分配给子节点一些步数后,可能还会回到i节点,所以需要考虑到底回不回i节点的问题,解决方法就是多加一维记录是否回到i节点。
dp[i][j][0]表示不回,dp[i][j][1]表示回到i节点。
如果要回到i节点,那么就必须多留出2步,如果不回到i节点,那么只要1步。

代码

#pragma comment(linker, "/STACK:1024000000,1024000000") //加栈
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
#include <set>
#include <string>
#include <math.h>
#include <stack>
using namespace std;
typedef long long ll;
const int maxn = 3e2+8;
#define inf 1000000000
int n,m;
vector<int> g[maxn];
int h[maxn];
int dp[maxn][300][2];
void dfs(int u,int pre)
{
for(int i=0;i<=m;i++) dp[u][i][0]=dp[u][i][1]=h[u];
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(v==pre) continue;
dfs(v,u);
for(int j=m;j>=1;j--)
{
for(int k=1;k<=j;k++)
{
dp[u][j][0]=max(dp[u][j][0],dp[u][j-k][1]+dp[v][k-1][0]);
dp[u][j][0]=max(dp[u][j][0],dp[u][j-k][0]+dp[v][k-2][1]);
dp[u][j][1]=max(dp[u][j][1],dp[u][j-k][1]+dp[v][k-2][1]);
}
}
}
}
int main(int argc, char const *argv[])
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++) g[i].clear();
for(int i=1;i<=n;i++)
{
scanf("%d",&h[i]);
}
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,0);
printf("%dn",max(dp[1][m][0],dp[1][m][1]));
}
return 0;
}

最后

以上就是霸气火为你收集整理的Apple Tree POJ - 2486(三维 树形背包)思路的全部内容,希望文章能够帮你解决Apple Tree POJ - 2486(三维 树形背包)思路所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(59)

评论列表共有 0 条评论

立即
投稿
返回
顶部