注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 4939 Stupid Tower Defense  

2014-08-13 20:44:43|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=4939
多校合练第7场第5题。
题意:
三种塔,n单位直线,告诉每种塔的性质,问如何安排能产生最大的伤害。
红塔:经过当前位置,每秒x伤害;
绿塔:该位置之后,每秒y伤害;
蓝塔:该位置之后,每个单位增加z时间。
题解:
首先红塔肯定放最后,这样伤害最大,则用dp[i][j]表示前i单位j个蓝塔的最大伤害。
r1=dp[i-1][j]+(max(0,i-j-1))*(t+j*z)*y;
r2=dp[i-1][j-1]+(i-j)*y*(t+(j-1)*z);
dp[i][j]=max(r1,r2);

LL n,x,y,z,t;
LL dp[1510][1510];

void fun()
{
MEM(dp);
LL ans=n*t*x;
for(LL i=1;i<=n;i++) //danwei
{
for(LL j=0;j<=i;j++) //lan
{
if(j == 0)
dp[i][0]=dp[i-1][0]+t*(i-1)*y;
else
{
LL r1=dp[i-1][j]+(max(0LL,i-j-1))*(t+j*z)*y;
LL r2=dp[i-1][j-1]+(i-j)*y*(t+(j-1)*z);
dp[i][j]=max(r1,r2);
}
ans=max(ans,dp[i][j]+(n-i)*(x+(i-j)*y)*(t+j*z));
}
}
pf64(ans);
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
int T,cas=1;
sf(T);
while(T--)
{
printf("Case #%d: ",cas++);
sf64(n);sf264(x,y);sf264(z,t);
fun();
}
return 0;
}


  评论这张
 
阅读(72)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017