HDU 4939 Stupid Tower Defense

题目链接~~>

做题感悟：开始看着题很明显的 dp 但是dp 到最后也没 dp 出来，做完这题之后发现其实有些 dp 需要一些贪心的思想，然后再dp一下。

解题思路：

                   三种塔都有各自的功能，就和英雄杀里的人物技能一样，绿塔和蓝塔貌似为红塔做铺垫，绿塔负责增加伤害，蓝塔负责增加时间，和英雄杀里宋江，西施，商鞅三个人的配合差不多，只有相互配合才使得伤害最大化。扯远了，回到这题，直接附上官方题解：

代码：

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<fstream>
     
    
   

    

     

    
    

     

      #include<iomanip>
     
    
   

    

     

    
    

     

      #include<ctime>
     
    
   

    

     

    
    

     

      #include<fstream>
     
    
   

    

     

    
    

     

      #include<sstream>
     
    
   

    

     

    
    

     

      #include<stack>
     
    
   

    

     

    
    

     

      #include<cstring>
     
    
   

    

     

    
    

     

      #include<cmath>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<cstdio>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      #define INT __int64
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      const double esp = 0.00000001 ;
     
    
   

    

     

    
    

     

      const INT INF = 1000000000 ;
     
    
   

    

     

    
    

     

      const INT MY = 20 ;
     
    
   

    

     

    
    

     

      const INT MX = 1500 + 10 ;
     
    
   

    

     

    
    

     

      INT dp[MX][MX] ;
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       INT Tx ,cse = 1 ,n ,x ,y ,z ,t ;
     
    
   

    

     

    
    

     
 scanf("%I64d" ,&Tx) ;
     
    
   

    

     

    
    

     
 while(Tx--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%I64d%I64d%I64d%I64d%I64d" ,&n ,&x ,&y ,&z ,&t) ;
     
    
   

    

     

    
    

     

       INT ans = n*t*x ;
     
    
   

    

     

    
    

     
 memset(dp ,0 ,sizeof(dp)) ;
     
    
   

    

     

    
    

     
 for(INT i = 1 ;i <= n ;i++)
     
    
   

    

     

    
    

     
 for(INT j = 0 ;j <= i ;j++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(!j)  dp[i][0] = dp[i-1][0] + t*y*(i-1) ;  // 全为蓝塔
     
    
   

    

     

    
    

     
 else dp[i][j] = max(dp[i-1][j-1] + (i-j)*y*(t+(j-1)*z) ,dp[i-1][j] + (i-1-j)*y*(t+j*z)) ;
     
    
   

    

     

    
    

     

       ans = max(dp[i][j] + (t+j*z)*(n-i)*x + (i-j)*y*(t+j*z)*(n-i) ,ans) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 cout<<"Case #"<<cse++<<": "<<ans<<endl ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return  0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/38611047