poj 3345(树形dp)-白红宇

poj 3345(树形dp)

阅读量：5956 次

发布时间：2019-06-19

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

题意：一个人要买通若干支持者，这些支持者的关系形成一棵森林，只要买通树根他的孩子节点也会被买通，问你至少要买通m个守卫要花多少钱。

思路：由于是一颗森林我们需要加一个结点使得他到每个点都建一条边，然后dp[i][j]表示i为根的结点买通j个需要的最小花费。

dp[v][j] = min(dp[v][j], dp[v][j-k] + dp[x][k]);

代码如下：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
              9 #include 
              
               10 #include 
               
                11 #define MP(a, b) make_pair(a, b)12 #define PB(a) push_back(a)13 using namespace std;14 15 const int LEN = 210;16 const int INF = 0x3f3f3f3f;17 int n, m, vex[LEN], dp[LEN][LEN], ind[LEN], top;18 vector
                
                  Map[LEN];19 map
                 
                   mp;20 21 int ch(string s){22 if(!mp.count(s))mp[s] = top++;23 return mp[s];24 }25 26 int dfs(int v, int fa){27 int ret = 1;28 dp[v][0] = 0;29 for(int i=0; i
                  
                   =0; j--){34 for(int k=0; k<=j; k++){35 dp[v][j] = min(dp[v][j], dp[v][j-k] + dp[x][k]); 36 }37 }38 }39 }40 dp[v][ret] = min(dp[v][ret], vex[v]);41 return ret;42 }43 44 int main()45 {46 freopen("in.txt", "r", stdin);47 48 char buf[LEN], na[LEN], nb[LEN];49 int tn, a, b;50 while(scanf("%s", buf)!=EOF){51 if(buf[0] == '#') break;52 for(int i=0; i

View Code

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

你可能感兴趣的文章