HDU 3008 Warcraft
阅读原文时间:2023年07月09日阅读:1

题意:一个人有100点血和100点魔法,Boss有100点血。人有n个技能。每一个技能对Boss有a[i]点伤害,

且会消耗b[i] 的点魔量,人每秒会有t秒魔法恢复(最大为100)Boss每秒有q点伤害,问人能否先击败Boss

若能。须要几秒。

dp[i][tmp]:在第 i 秒 剩余 魔法为 tmp 时的伤害。

tmp = 第i秒拥有的魔法 j - a[k]消耗的魔法+t。

dp[i][tmp]=max(dp[i][tmp]。dp[i-1][第i秒拥有的魔法 j]+b[k]);

每次找出第 i 秒时有 j 魔法剩余tmp魔法的伤害。

理解:在第 i-1 秒时有 j 点魔法,然后 在 第 i 秒时用第 i-1 秒时的魔法使用第 k个技能 攻击Boss

攻击完后剩余tmp点魔法,以此循环……

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define INF 1e8
#define eps 1e-8
#define LL long long
#define maxn 100001
#define mol 1000000007

int main()
{
int n,t,q;
int dp[105][105];
int a[105],b[105];
while(scanf("%d%d%d",&n,&t,&q))
{
if(n==0&&t==0&&q==0) break;
for(int i=1;i<=n;i++) { scanf("%d%d",&a[i],&b[i]); } memset(dp,0,sizeof(dp)); a[0]=0;b[0]=1; int flag=0,i; for(i=1;(i-1)*q<100;i++) { for(int j=0;j<=100;j++) { for(int k=0;k<=n;k++) { if(j100) tmp=100;
if(dp[i][tmp]=100)
{
flag=1;
break;
}
}
if(flag) break;
}
if(flag) break;
}
if(flag)
printf("%d\n",i);
else printf("My god\n");
}
return 0;
}

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章