POJ 3345 Bribing FIPA 树形DP-白红宇

POJ 3345 Bribing FIPA 树形DP

阅读量：6836 次

发布时间：2019-06-26

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

题目链接:

题意:

一个国家要参加一个国际组织, 需要n个国家投票, n个国家中有控制和被控制的关系, 形成了一颗树.

比如: 国家C被国家B控制, 国家B被国家A控制, 那么B , C 会跟着A投同一家国家. 而要有些国家给它投票,

就得用若干钻石去贿赂那些国家. 最后问, 要到至少有m个国家投它的票, 最少需要多少钻石.

分析: 对于每一个结点只有两种状态, 选与不选, 所以dp方程里加上一维即可.

dp[i][j][k], 表示在i的子结点中,选j个最少需要的钻石数, 另k=1表示选i本身,k=0表示不选

dp[cnt][j+k][0] = min( dp[cnt][j+k][0], dp[cnt][j][0] + min(dp[son][k][0],dp[son][k][1]) );

代码:

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         using namespace std;const int inf=0xFFFFFFF;vector
          
           N[205];vector
           
            M[205];map
            
             Map;int h[205],dp[205][205][2]; /// dp[i][j][k] k=0表示不选i,反之则选int n,m;void Init(){ for(int i=0;i<=n;++i){ N[i].clear(); M[i].clear(); for(int j=0;j<=n;++j) dp[i][j][1]=dp[i][j][0]=inf; } memset(h,0,sizeof(h));}void DFS(int cnt){ int len=M[cnt].size(); h[cnt]=len; for(int i=0;i
             
              =0; --j) for(int k=m-j; k>=0; --k) dp[cnt][j+k][0]=min(dp[cnt][j+k][0],dp[cnt][j][0]+min(dp[son][k][0],dp[son][k][1])); }}int main(){ while(cin>>n>>m){ Init(); for(int i=1;i<=n;++i){ string s; cin>>s>>dp[i][1][1]; Map[s]=i; char c; scanf("%c",&c); while(c!='\n'){ cin>>s; N[i].push_back(s); scanf("%c",&c); } } for(int i=1;i<=n;++i){ int len=N[i].size(); for(int j=0;j