poj1155TELE - 樹形dp

這題和上一題一樣的思路，不過背包的體積有不同，每次都要計算

[cpp]
#include<iostream>  
#include<cstdio>  
#include<cstring>  
#include<vector>  
using namespace std; 
 
int N,M,v[3010]; 
vector<int>son[3010];         //記錄兒子節點   
vector<int>cost[3010];            //記錄花費   
int dp[3010][3010]; 
 
int dfs(int n){ 
    int sum=0,len=son[n].size(); 
    dp[n][0]=0; 
    if(n>N-M){ 
        dp[n][1]=v[n]; 
        return 1; 
    } 
     
    for(int i=0;i<len;i++) 
    { 
        int num=dfs(son[n][i]); 
        sum+=num; 
        for(int j=sum;j>=1;j--) 
            for(int k=1;k<=num&&k<=j;k++) 
                if(dp[n][j]<dp[n][j-k]+dp[son[n][i]][k]-cost[n][i]) 
                    dp[n][j]=dp[n][j-k]+dp[son[n][i]][k]-cost[n][i]; 
    } 
    return sum; 
} 
 
 
int main() 
{ 
    int i,j,k,a,c,ans; 
     
    while(scanf("%d%d",&N,&M)!=EOF) 
    { 
        ans=0; 
        memset(dp,-12345,sizeof(dp)); 
        for(i=0;i<=N;i++)    son[i].clear(); 
        for(i=1;i<=N-M;i++){ 
            scanf("%d",&k); 
            for(j=1;j<=k;j++){ 
                scanf("%d%d",&a,&c); 
                son[i].push_back(a); 
                cost[i].push_back(c); 
            } 
        } 
        for(i=N-M+1;i<=N;i++){//本來寫的是for(i=1;i<=M;i++) ,,錯了很久才發現   
            scanf("%d",&v[i]); 
        //  printf("%d ",v[i]);  
        }// printf("~\n");  
         
        dfs(1); 
        for(i=M;i>=1;i--) 
            if(dp[1][i]>=0){ 
                printf("%d\n",i); 
                break; 
            } 
    } 
    return 0; 
} 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;

int N,M,v[3010];
vector<int>son[3010];   //記錄兒子節點
vector<int>cost[3010];   //記錄花費
int dp[3010][3010];

int dfs(int n){
 int sum=0,len=son[n].size();
 dp[n][0]=0;
 if(n>N-M){
  dp[n][1]=v[n];
  return 1;
 }
 
 for(int i=0;i<len;i++)
 {
  int num=dfs(son[n][i]);
  sum+=num;
  for(int j=sum;j>=1;j--)
   for(int k=1;k<=num&&k<=j;k++)
    if(dp[n][j]<dp[n][j-k]+dp[son[n][i]][k]-cost[n][i])
     dp[n][j]=dp[n][j-k]+dp[son[n][i]][k]-cost[n][i];
 }
 return sum;
}

int main()
{
 int i,j,k,a,c,ans;
 
 while(scanf("%d%d",&N,&M)!=EOF)
 {
  ans=0;
  memset(dp,-12345,sizeof(dp));
  for(i=0;i<=N;i++) son[i].clear();
  for(i=1;i<=N-M;i++){
   scanf("%d",&k);
   for(j=1;j<=k;j++){
    scanf("%d%d",&a,&c);
    son[i].push_back(a);
    cost[i].push_back(c);
   }
  }
  for(i=N-M+1;i<=N;i++){//本來寫的是for(i=1;i<=M;i++) ,,錯了很久才發現
   scanf("%d",&v[i]);
  // printf("%d ",v[i]);
  }// printf("~\n");
  
  dfs(1);
  for(i=M;i>=1;i--)
   if(dp[1][i]>=0){
    printf("%d\n",i);
    break;
   }
 }
 return 0;
}