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 __int64
using 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的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 飞桨抠图直播2020.4.1
- 下一篇： 飞桨 第一课 传统图像识别是怎么做的+A