HDU 4939 Stupid Tower Defense
【摘要】 题目链接~~>
做题感悟:开始看着题很明显的 dp 但是dp 到最后也没 dp 出来,做完这题之后发现其实有些 dp 需要一些贪心的思想,然后再dp一下。
解题思路:
三种塔都有各自的功能,就和英雄杀里的人物技能一样,绿塔和蓝塔...
做题感悟:开始看着题很明显的 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
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)