首页 > 代码库 > poj 2486 a apple tree
poj 2486 a apple tree
题意：n节点的树，从1开始走,总共v步，每个点都有一个价值，求可以获得的最大价值分析：这个显然可以走回来，那么就加一维表示是否走回祖先dp[u][i][j]表示从u为根节点的子树，往下走i步，j=0表示不走回来,j=1表示走回来那么可以得到状态转移方程，不走回来的可能会影响走回来的，如果先算不会来的，那么一个节点在不走回来算一次在走回来又算一次，所以先算走回来的就可以避免dp[u][i][0]=max(dp[u][i][0],dp[u][i-j][1]+dp[v][j-1][0]);dp[u][i][0]=max(dp[u][i][0],dp[u][i-j][0]+dp[v][j-2][1]);dp[u][i][1]=max(dp[u][i][1],dp[u][i-j][1]+dp[v][j-2][1]);#include#include#include#include#includeusing namespace std;const int maxn=505;vector g[maxn];int val[maxn],n,k,dp[maxn][205][2];void dfs(int u,int f){ for(int i=0;i0;i--) for(int j=1;j<=i;j++){ dp[u][i][0]=max(dp[u][i][0],dp[u][i-j][1]+dp[v][j-1][0]); dp[u][i][0]=max(dp[u][i][0],dp[u][i-j][0]+dp[v][j-2][1]); dp[u][i][1]=max(dp[u][i][1],dp[u][i-j][1]+dp[v][j-2][1]); } }}int main(){ //freopen("in","r",stdin); ios::sync_with_stdio(false); while(cin>>n>>k){ memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++){ cin>>val[i];g[i].clear(); for(int j=0;j<=k;j++) dp[i][j][0]=dp[i][j][1]=val[i]; } for(int i=1;i>u>>v; g[u].push_back(v);g[v].push_back(u); } dfs(1,-1); cout<poj 2486 a apple tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。