hdu 1011（树形dp）-白红宇

hdu 1011（树形dp）

阅读量：5905 次

发布时间：2019-06-19

本文共 1141 字，大约阅读时间需要 3 分钟。

Mark。看着吴神博客写的，还未完全懂。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
              9 #include 
              
               10 #include 
               
                11 #include 
                
                 12 #include 
                 
                  13 #define MP(a, b) make_pair(a, b)14 #define PB(a) push_back(a)15 using namespace std;16 17 const int LEN = 2010;18 int W[LEN], V[LEN], n, m, dp[LEN][LEN];19 vector
                  
                    Map[LEN];20 21 void dfs(int v, int fa){22 for(int i=0; i
                   
                    =V[v]; k--){27 for(int j=1; j<=m; j++){28 if(k>=j+V[v])dp[v][k] = max(dp[v][k], dp[v][k-j] + dp[x][j]);29 }30 }31 }32 }33 for(int i=V[v]; i<=m; i++) dp[v][i] += W[v];34 }35 36 int main()37 {38 // freopen("in.txt","r",stdin);39 //freopen("out.txt","w",stdout);40 41 int a, b;42 while(cin >> n >> m){43 if(n < 0 && m < 0) break;44 for(int i=0; i
                    
                     > V[i] >> W[i];48 V[i] = (V[i]+19)/20;49 }50 for(int i=0; i
                     
                      > a >> b;52 a--, b--;53 Map[a].PB(b);54 Map[b].PB(a);55 }56 dfs(0, -1);57 if(!m) cout << 0 << endl;58 else cout << dp[0][m] << endl;59 }60 return 0;61 }