2017.10.26模拟 b energy

2017.10.26模拟 b energy

​​ “`

#include

include

define N 1100

define inf 0x3f3f3f3f

include

using namespace std; inline char gc(){ static char now[1<<16],*T,*S; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++; } inline int read(){ int x=0;char ch=getchar(); while (ch<’0’||ch>’9’) ch=getchar(); while (ch>=’0’&&ch<=’9’){x=x*10+ch-‘0’;ch=getchar();} return x; } struct node{ int y,next; }data[N]; int dp[N][110],value[N],edge[N],ans,h[N],n,num; void dfs(int x){ if (x==0) return; for (int i=h[x];i;i=data[i].next){ int y=data[i].y; dfs(y); for (int j=edge[x];j>=0;–j){ for (int j1=0;j1<=j;++j1){ dp[x][j]=max(dp[y][j1]+dp[x][j-j1],dp[x][j]); }

}}for (int i=edge[x];i>=value[x];--i) dp[x][i]=max(dp[x][i-value[x]]+1,dp[x][i]);

} int main(){ freopen(“energy.in”,”r”,stdin); n=read(); for (int i=1;i<=n;++i){ int fa1=read();value[i]=read();edge[i]=read(); data[++num].y=i;data[num].next=h[fa1];h[fa1]=num; }//memset(dp,0x3f,sizeof(dp));memset(dp[0],0,sizeof(dp[0])); for (int i=h[0];i;i=data[i].next){ int y=data[i].y;dfs(y); ans+=dp[y][edge[y]]; } printf(“%d”,ans); return 0; } “`

树形dp一开始写挂一波 其实 这个按照背包思想就很好写了

我枚举dp[x][j]表示x个节点我可以给j能量 然后这j个能量可以分给一号子树 二号 三号

这么多怎么办 想想飞扬的小鸟 所有的状态可以根据背包的做法只从前一个转移过来就好 就不会tle

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