首页 > 代码库 > hdu 4939 Stupid Tower Defense (dp)
hdu 4939 Stupid Tower Defense (dp)
题目大意:
简单的塔防游戏,有三种塔。
一种是减速塔,只能减速它身后的敌人,使之移动速度减慢。通过一格的时间变成加z秒。
两种攻击塔,一种只能打面前,另外一种可以打身后。
思路分析:
我们默认把只能攻击面前的塔放到最后面。
状态方程: dp [i] [j] 表示放到第 i 个位置放了 j 个防御塔能达到的最大伤害。
转移方程:dp [i] [j] =max ( dp[i-1][j] + buildy , dp[i-1][j-1] + buildz )
buildy 表示第 i 位置建一个 攻击塔使后面多出来的伤害。
buildz 表示第 i 位置建一个 减速塔使后面多出来的伤害。
怎么计算buildy buildz 就是通过减去之前的伤害然后重新计算伤害 。
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #define maxn 1505 using namespace std; typedef long long ll; ll dp[maxn][maxn]; int main() { ll n,x,y,z,t; int cas=1; int T; scanf("%d",&T); while(T--) { scanf("%I64d%I64d%I64d%I64d%I64d",&n,&x,&y,&z,&t); memset(dp,0,sizeof dp); dp[0][0]=n*x*t; for(int i=1;i<=n;i++) { for(int j=0;j<=i;j++) { if(j==0) { dp[i][j]=t*((2*n-i-1)*i/2)*y+(n-i)*t*x; } else { ll buildz = dp[i-1][j-1]-(n-i+1)*(t+z*(j-1))*x+(n-i)*((t+z*(j-1))+z)*x-(n-i)*(i-j)*y*(t+(z*(j-1)))+(n-i)*(i-j)*y*(t+z*j); if(i==j)buildy=(t+j*z)*(n-i)*x; else buildy = dp[i-1][j]-(n-i+1)*(t+z*j)*x+(n-i)*(t+z*j)*x+(n-i)*(t+z*j)*y; dp[i][j]=max(buildz,buildy); } } } ll ans=0; for(int i=0;i<=n;i++) for(int j=0;j<=i;j++) { ans=max(ans,dp[i][j]); } printf("Case #%d: %I64d\n",cas++,ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。