HDU4044 GeoDefense（树形dp+分组背包）-白红宇

HDU4044 GeoDefense（树形dp+分组背包）

阅读量：6991 次

发布时间：2019-06-27

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

题意：

给定n个节点组成的树，1为敌方基地，叶子结点为我方结点。我们可以在每个结点安放炮台，至多一炮，然后就可以打炮，每个结点有ki种炮，每种炮有一个花费和一个能量（能量对应着打掉敌人多少hp）。敌人可能往一个结点的每条分支跑，所以要想保证守住阵地，就要保证每个分支都要安放炮台。最后问怎么打炮，才能使打掉的敌人hp最多。

思路：

树形dp，dp[i][j]表示以i为根节点消耗j能量所打掉的最大hp

这道题有个坑，就是建炮的花费有可能是0，这样需要处理一下，避免建多个炮。

先附上自己的代码（889ms）：

/* ***********************************************Author        :devilCreated Time  :2016/3/29 16:54:34************************************************ */#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               #include 
               
                using namespace std;#define inf 0x7f7f7f7f#define N 1010#define M 210int n,m,dp[N][M];vector
                
                 eg[N];vector
                 
                  price[N],power[N];void init(){ for(int i=0;i
                  
                   =0;j--) { int tmp=0; for(int k=0;k<=j;k++) tmp=max(tmp,min(dp[u][j-k],dp[to][k])); dp[u][j]=tmp; } } for(int i=m;i>=0;i--) { int tmp=dp[u][i]; for(int j=0;j

然后又参考了网上的另一种做法，把每个节点每种花费的最大hp消耗存在数组里，写起来方便些，遍历的要多，时间复杂度要高一些，附上代码（998ms）：

/* ***********************************************Author        :devilCreated Time  :2016/3/29 16:58:28************************************************ */#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               #include 
               
                using namespace std;#define inf 0x7f7f7f7f#define N 1010#define M 210int n,m,dp[N][M],hp[N][M];vector
                
                 eg[N];void init(){ for(int i=0;i
                 
                  =0;j--) { int tmp=0; for(int k=0;k<=j;k++) tmp=max(tmp,min(dp[u][j-k],dp[to][k])); dp[u][j]=tmp; } } for(int i=m;i>=0;i--) for(int j=0;j<=i;j++) dp[u][i]=max(dp[u][i],dp[u][i-j]+hp[u][j]);}int main(){ //freopen("in.txt","r",stdin); int t,x,y,q; scanf("%d",&t); while(t--) { init(); scanf("%d",&n); for(int i=1;i

转载于:https://www.cnblogs.com/d-e-v-i-l/p/5333628.html

你可能感兴趣的文章