首页 > 代码库 > HDU_4939 stupid tower defense 2014多校7 多变量型DP
HDU_4939 stupid tower defense 2014多校7 多变量型DP
意思是有个塔防游戏,有三种塔,红塔在怪物经过的时候每秒会产生攻击力大小的伤害,绿塔对怪物经过以及经过之后每秒产生攻击力大小的伤害,还有种蓝塔,对怪物进行减速,即怪物从此之后经过一个单位都会减慢c秒
最后最最大的伤害值是多少
又是比赛的时候没想出来,知道是个DP,但是对这种多变量型的DP就是有点不感冒。这个思想其实也是差不多的,你首先得枚举其中的一个值或者两个值
这里有个特性,我绿塔和蓝塔放越前面越好,红塔放越后面越好(主要是腾前面的位置给另外两种),这用了点贪心技巧,但绝对是对的
所以我们可以枚举某个点 后面全部是放红塔。。。然后我绿塔和蓝塔该怎么处理呢。这个时候我们不能猛想全局,考虑单个点的伤害,前面是绿和蓝,后面是红,这样在这个点所受的伤害,我枚举前面蓝塔有几个,则绿塔就是长度-蓝的数目,这样对该点的伤害我就可以求出来,然后通过i-1过渡出来,就可以得到整个前段受的伤害,再通过直接算出后面红塔的伤害,就可以得出这个状态下受到的总伤害,最后取最大值即可
#include <iostream>#include <cstdio>#include <cstring>#define LL __int64using namespace std;LL dp[1510][1510];int main(){ int w,kase=0; LL n,x,y,z,t; scanf("%d",&w); while (w--) { memset(dp,0,sizeof dp); scanf("%I64d%I64d%I64d%I64d%I64d",&n,&x,&y,&z,&t); LL ans=0; for (int i=1;i<=n;i++){ for (int j=0;j<=i;j++){ if(j<i) dp[i][j]=dp[i-1][j]+((i-1-j)*z+t)*j*y; if (j>0){ dp[i][j]=max(dp[i][j],dp[i-1][j-1]+((i-j)*z+t)*(j-1)*y); } ans=max(ans,dp[i][j]+((i-j)*z+t)*(n-i)*(x+j*y)); } } ans=max(ans,n*t*x); printf("Case #%d: ",++kase); printf("%I64d\n",ans); }}
HDU_4939 stupid tower defense 2014多校7 多变量型DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。