hdu 1561（树形dp）-白红宇

hdu 1561（树形dp）

阅读量：7082 次

发布时间：2019-06-28

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

说好的开始搞树形DP，前两天一直沉迷于游戏之中，昨天又玩了一整天炉石。ORZ

今天搞搞憋出了第一道。中文题就不说题意了

思路：dp[i][j]表示以i为根的子树攻克j个城堡的最大收获。一开始的时候要加一个零号结点上去，指向所有能被直接攻克的点。然后初始dp[v][1] = vex[v]（状态转移从1开始）原因是先要攻克根才能攻克子树所以要更新子树的话根是一定要被攻克的。然后dp[v][k+j] = max(dp[v][k+j], dp[v][k]+dp[ch][j]) ch枚举每颗子树。

代码如下：

1 /************************************************** 2  * Author     : xiaohao Z 3  * Blog     : http://www.cnblogs.com/shu-xiaohao/ 4  * Last modified : 2014-04-02 11:38 5  * Filename     : hdu_1561.cpp 6  * Description     :  7  * ************************************************/ 8  9 #include 
      
       10 #include 
       
        11 #include 
        
         12 #include 
         
          13 #include 
          
           14 #include 
           
            15 #include 
            
             16 #include 
             
              17 #include 
              
               18 #include 
               
                19 #include 
                20 #define MP(a, b) make_pair(a, b)21 #define PB(a) push_back(a)22 23 using namespace std;24 typedef long long ll;25 typedef pair
                 
                   pii;26 typedef pair
                  
                    puu;27 typedef pair
                   
                     pid;28 typedef pair
                    
                      pli;29 typedef pair
                     
                       pil;30 31 const int INF = 0x3f3f3f3f;32 const double eps = 1E-6;33 const int LEN = 1010;34 vector
                      
                        Map[LEN];35 int n, m, vex[LEN], dp[LEN][LEN], num[LEN];36 37 int dfs(int v, int f){38 num[v] = 1;39 dp[v][1] = vex[v];40 for(int i=0; i
                       
                        0; k--)49 for(int j=0; j<=num[ch]; j++){50 dp[v][k+j] = max(dp[v][k+j], dp[v][k]+dp[ch][j]);51 }52 }53 }54 return num[v];55 }56 57 int main()58 {59 // freopen("in.txt", "r", stdin);60 61 int a;62 while(cin >> n >> m){63 if(!n && !m) break;64 for(int i=0; i
                        
                         > a >> vex[i];69 Map[a].PB(i);70 }71 dfs(0, -1);72 cout << dp[0][m+1] << endl;73 }74 return 0;75 }

View Code

转载于:https://www.cnblogs.com/shu-xiaohao/p/3640380.html

你可能感兴趣的文章