hdu 4044 树形DP 炮台打怪（好题）-白红宇

hdu 4044 树形DP 炮台打怪（好题）

阅读量：5237 次

发布时间：2019-06-14

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

题目链接：

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

参考链接：http://blog.csdn.net/woshi250hua/article/details/7683765

这道题敌人走的是随意路线，意味着要所有叶子节点中最小的那条路线要越大越好。所以dp[fa][j]保存的是fa结点到所有叶子节点中最小值。

给的费用是定值，首先遍历得到tp[i][j]，表示i结点j费用最大的价值。

然后dfs，给叶子节点赋值，非叶子节点为INF（为了得到叶子节点的信息），叶子节点遍历完后才加上根节点的值。具体看代码

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  #include 
                   
                    using namespace std;#define mem(a,b) memset(a,b,sizeof(a))#define pf printf#define sf scanf#define spf sprintf#define pb push_back#define debug printf("!\n")#define MAXN 1000+5#define MAX(a,b) a>b?a:b#define blank pf("\n")#define LL long long#define ALL(x) x.begin(),x.end()#define INS(x) inserter(x,x.begin())#define pqueue priority_queue#define INF 0x3f3f3f3fint n,m;struct node{ int y,val,next;}tree[MAXN<<2];int head[MAXN],vis[MAXN],ptr=1,dp[MAXN][MAXN];int price[MAXN][MAXN],power[MAXN][MAXN],a[MAXN],tp[MAXN][MAXN];void init(){ mem(head,-1); mem(vis,0); mem(dp,INF); mem(tp,0); ptr=1;}void add(int x,int y){ tree[ptr].y = y; tree[ptr].next = head[x]; head[x] = ptr++;}void dfs(int rt,int fa){ vis[rt]=1; //pf("t%d %d\n",rt,head[rt]); if(head[rt]==-1) { for(int i = m;i>=0;i--) { dp[rt][i] = tp[rt][i]; //pf("r%d %d %d\n",rt,i,dp[rt][i]); } return; } for(int i = head[rt];i!=-1;i=tree[i].next) { int y = tree[i].y; if(vis[y]) continue; dfs(y,rt); for(int j=m;j>=0;j--) { int t = 0; for(int k=0;k<=j;k++) { t = max(t,min(dp[rt][j-k],dp[y][k])); } dp[rt][j] = t; } } for(int j = m;j>=0;j--) { for(int k=0;k<=j;k++) dp[rt][j] = max(dp[rt][j],dp[rt][j-k]+dp[rt][k]); }}int main(){ int i,j,k,t; sf("%d",&t); while(t--) { init(); sf("%d",&n); for(i=1;i

还有第二个解法，多叉树转二叉树：

http://blog.csdn.net/shuangde800/article/details/10523547

转载于:https://www.cnblogs.com/qlky/p/5828048.html

你可能感兴趣的文章