首页 > 代码库 > HDU 4939 Stupid Tower Defense dp
HDU 4939 Stupid Tower Defense dp
题意:给你一段长为n的路,每一个单位长度可以放一种塔,这里有三种塔。
1)对正在经过这座塔的敌人进行 x 每秒伤害的攻击
2)对于已经经过这塔的敌人进行y每秒的伤害攻击
3)对已经经过这个塔的敌人放慢速度,使得原先为 经过一个单位时间为 t的速度变为 t+k
解题思路:我们可以知道,第一种塔一定是放在最后面的,然后进行DP,DP[i][j] 代表经过了 i 座塔其中有 j 座是第二种塔的最大值(其余的是第三种塔),对每一个dp[i][j]计算总时间就行。
状态转移方程为 dp[i][j] = max(dp[i-1][j-1] + y*(j-1)*(t+(i-j)*k) , dp[i-1][j] + y*j*(t +(i-j-1)*k))
但是在考虑状态的时候要特别注意对于j == i 的情况 ,这种情况是没有 dp[i-1][j]的 比赛的时候竟是因为这里没有考虑导致了一直找不出bug,所以这里还是需要把问题都考虑全面。
解题代码:
1 // File Name: 1005.cpp 2 // Author: darzdream 3 // Created Time: 2014年08月12日 星期二 12时25分19秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque>10 #include<bitset>11 #include<algorithm>12 #include<functional>13 #include<numeric>14 #include<utility>15 #include<sstream>16 #include<iostream>17 #include<iomanip>18 #include<cstdio>19 #include<cmath>20 #include<cstdlib>21 #include<cstring>22 #include<ctime>23 #define LL long long24 25 using namespace std;26 LL n ,x , y , z , t ;27 LL ans = 0 ; 28 LL dp[1600][1602];// 前I 个塔选多少个y塔。29 void solve()30 {31 for(int i = 0;i <= n ;i ++ )32 for(int j =0 ;j <= n;j ++)33 {34 dp[i][j] = 0; 35 }36 ans = x*n*t;37 for(int i = 1 ;i <= n;i ++)38 {39 for(int j = 0;j <= i ;j ++)40 {41 if(j >= 1)42 {43 dp[i][j] = max(dp[i-1][j-1] + y*(j-1)*(t+(i-j)*z), dp[i-1][j] + y*j*(t+(i-1-j)*z)); // maybe wa44 if(i == j )45 {46 dp[i][j] = dp[i-1][j-1] + y*(j-1)*(t+(i-j)*z); // maybe wa47 }48 }49 if(dp[i][j] + (x + j* y)*(t+(i-j)*z)*(n-i) > ans)50 {51 ans = dp[i][j] + (x + j * y)*(t+(i-j)*z)*(n-i) ;52 }53 }54 }55 }56 int main(){57 int T;58 //freopen("input","r",stdin);59 //freopen("output1","w",stdout);60 scanf("%d",&T);61 for(int ca = 1; ca <= T ;ca ++)62 {63 scanf("%I64d %I64d %I64d %I64d %I64d",&n,&x,&y,&z,&t);64 solve(); 65 printf("Case #%d: %I64d\n",ca,ans);66 }67 return 0;68 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。