HDOJ 1770 - 阅读理解...树形DP

HDOJ 1770 - 阅读理解...树形DP

题意: 一个能量E可以通过吸收某个光子的能量变成E1或者释放某个光子的能量变成E2...并且任意两个能量的转化路径至多一条...现在有一堆能量,有一堆光子...如果某个能量与某个光子做直接运算(加上其能量或者减去)会等于一个已经存在的能量...那么就会发生危险...问在这堆能量中..不发生危险并且能量和最大为多少...

由于两个能量的转化路径至多一条..那么可以用树(森林)来表示所有的关系...有冲突的两点做无向边....我之前一直WA就是做成有向边了...

dp[k][0]代表以k为根的子树,不取k这个点..最多能获得的能量...

dp[k][1]代表以k为根的子树,取k这个点..最多能获得的能量...

转化成一个很经典的问题了..

Program:

#include#include#include#include#include#include#include#define ll long long#define oo 1000000007#define MAXN 205using namespace std; vector Tree[MAXN];int n,m,a[MAXN],dp[MAXN][2];bool P[1000005],used[MAXN],root[MAXN];void dfs(int x){ int i,num=Tree[x].size(); used[x]=true; dp[x][0]=0,dp[x][1]=a[x]; for (i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。