树形DP

---

　　一开始想：f[i][j]表示以 i 为根的子树，花 j 块钱能得到的最高力量值，结果发现转移的时候没法保证叶子结点的数量限制TAT

　　只好去膜拜题解了……在这里贴两篇泛型背包的文章吧：、

　　vfk的酷炫姿势没看懂……这篇题解应该讲的是比较清楚的一篇>_>  

这题算是把我对树形DP的闭塞理解给打通了一点。

我本认为树形DP只有用子节点的状态去更新父节点的状态，真是太天真了。

实际上这道题里是用子节点的状态合并得到父节点的状态。

首先，设出状态f[i][j][k]表示节点i对父亲的贡献为j付出的代价为k时i节点及其子树可以得到的最多能量。

        dp当然要从初始状态推起咯。

        那么对于那些叶子节点，也就是所谓的基本装备:

        f[i][j][j*cost[i]]=(j-i)*power[i]

然而对于那些非叶子节点:

          f[i][j][k]=max{g[k-r]+f[son][j*need[son]][r]};

这个方程具体点的解释可以理解为预算为k，拨给这个项目经费为r。

注意在这里我们并没有对f[i][j][k]中这一层中“私吞”部分进行统计，所以是j*need[son]，也就是假设全部先上交。

此处g数组是对上一次f[i][j]的复制，防止出现值的误调用。

此处循环考虑的因素比较多，所以总不能一边调用f[i][j]一边更新f[i][j]吧。memcpy多方便。

 

然后我们开始统计私吞部分:

          f[i][j][k]=max{f[i][j'][k]+(j'-j)*power[i]}

事实上,(j'-j)*power[i]就是没有用于合成(即上交)的i装备产生的能量。

非常巧妙，可惜这状态我想不到，还是经验问题。

Tips:注意挖掉一些非法状态和缩小lim范围。

 

1 /**************************************************************  2     Problem: 1017  3     User: Tunix  4     Language: C++  5     Result: Accepted  6     Time:8236 ms  7     Memory:48576 kb  8 ****************************************************************/  9   10 //BZOJ 1017 11 #include
      
        12 #include
       
         13 #include
        
          14 #include
         
           15 #include
          
            16 #include
           
             17 #define rep(i,n) for(int i=0;i
            
             =n;--i) 20 #define pb push_back 21 using namespace std; 22 inline int getint(){ 23 int v=0,sign=1; char ch=getchar(); 24 while(ch<'0'||ch>'9'){ if (ch=='-') sign=-1; ch=getchar();} 25 while(ch>='0'&&ch<='9'){ v=v*10+ch-'0'; ch=getchar();} 26 return v*sign; 27 } 28 const int N=55,INF=~0u>>2; 29 typedef long long LL; 30 /******************tamplate*********************/ 31 int n,m,ans=-INF; 32 struct node{ int to,v;}; 33 vector
             
              G[N]; 34 int f[N][110][2001],g[2001],cost[N],num[N],str[N],fa[N]; 35 void dfs(int x){ 36 if (!G[x].size()){ 37 num[x]=min(num[x],m/cost[x]); 38 F(i,0,num[x]) 39 F(j,i,num[x]) 40 f[x][i][j*cost[x]]=(j-i)*str[x]; 41 return; 42 }//DP边界：叶子结点 43 num[x]=INF; 44 rep(i,G[x].size()){ 45 dfs(G[x][i].to); 46 // cost[x]+=cost[G[x][i].to]*G[x][i].v; 47 num[x]=min(num[x],num[G[x][i].to]/G[x][i].v); 48 }//预处理合成装备的num和cost 49 F(i,0,num[x]) f[x][i][0]=0; 50 rep(i,G[x].size()){ 51 int to=G[x][i].to; 52 F(j,0,num[x]){ 53 memcpy(g,f[x][j],sizeof f[x][j]); 54 memset(f[x][j],-1,sizeof f[x][j]); 55 D(k,m,0){ 56 D(r,k,0) 57 if (g[k-r]!=-1 && f[to][j*G[x][i].v][r]!=-1) 58 f[x][j][k]=max(f[x][j][k],g[k-r]+f[to][j*G[x][i].v][r]); 59 ans=max(ans,f[x][j][k]); 60 } 61 } 62 } 63 F(i,0,num[x]) F(j,i,num[x]) F(k,0,m) 64 if (f[x][j][k]!=-1) 65 f[x][i][k]=max(f[x][i][k],f[x][j][k]+(j-i)*str[x]), 66 ans=max(ans,f[x][i][k]); 67 } 68 int main(){ 69 #ifndef ONLINE_JUDGE 70 freopen("1017.in","r",stdin); 71 freopen("1017.out","w",stdout); 72 #endif 73 n=getint(); m=getint(); 74 F(i,1,n){ 75 fa[i]=i; 76 num[i]=INF; 77 cost[i]=0; 78 } 79 char s1[5]; 80 F(i,1,n){ 81 str[i]=getint(); 82 scanf("%s",s1); 83 if (s1[0]=='B'){ 84 cost[i]=getint(); 85 num[i]=getint(); 86 }else{ 87 int c=getint(); 88 F(j,1,c){ 89 int x=getint(),y=getint(); 90 G[i].pb((node){x,y}); 91 fa[x]=i; 92 } 93 } 94 } 95 int root=0; 96 F(i,1,n) if (fa[i]==i){root=i;break;} 97 memset(f,-1,sizeof f); 98 dfs(root); 99 printf("%d\n",ans);100 return 0;101 }