2017.10.26模拟 b energy

​ ​http://www.elijahqi.win/archives/1391​​​
“`

#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]);
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
      
      

}
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