?

1191: 冰法斗神龍

Time Limit:?1 Sec??Memory Limit:?128 MB
Submit:?199??Solved:?15

Description

強大的冰魔法師zz一路過關闖將，終于獨自一人殺到了神龍面前。神龍的血量值為HP，正常狀態下每秒進行一次攻擊，傷害值為DAMAGE。zz精通n種瞬發冰控魔法（在同一秒內，zz發動的冰魔法要比神龍的攻擊快上一點），第i（1<=i<=n）種魔法傷害值為damage[i]，并使神龍進入冰凍狀態（神龍在冰凍狀態下不會進行攻擊，且如果神龍在冰凍狀態下再次受到冰魔法的攻擊，則冰凍時間累加），維持freeze[i]秒，使用完后有cd[i]秒的時間不得使用任何魔法。當zz與神龍有一方的血量值小于等于0時，即判定那一方死亡。zz想殺神龍，但是又怕死，所以請你幫他判斷一下以他現有的血量hp和他的技能，能否強殺神龍。

Input

第一行輸入整數T代表T組數據，T<=30

輸入數據的第一行為2個整數HP（0<HP<10^8） DAMAGE (0<DAMAGE<10^8) 分別代表神龍的血量值和神龍每次的攻擊值。

第二行也是2個整數hp(0<hp<10^8),n(1<=n<=1000000) 分別代表zz的血量以及zz會的魔法種類數。

第三行到n+2行每行均為3個整數damage[i](0<=damage<=100),freeze[i](0<=freeze[i]<=100),cd[i](1<=cd[i]<=100),(1<=i<=n)分別代表第i種魔法的傷害值，冰控時間，冷卻時間。

?

?

Output

輸出只有一行YES或NO，分別代表能殺死神龍和不能殺死神龍。

Sample Input

2 20 4 10 2 3 1 2 5 0 1 20 3 10 2 3 1 2 5 0 1

Sample Output

NO YES

HINT

Source

[Submit][Status][Web Board]

?

http://www.gdutcode.sinaapp.com/problem.php?id=1191

考慮到：只可能是一種技能最優，不可能你用著這個技能，然后用另一個，再用回來這個，這樣是不可能最優的。但可能是若干次A技能，然后選一次傷害最大的技能來用，最后一次用最大值來沖一沖。

然后有些情況是直接YES的。

1、如果wait[i] - fre[i]等于0，就是能一路壓著神龍，而且這個的攻擊力不能等于0

2、如果wait[i] - fre[i]小于0，就是能爭取自己的時間了，這時也不是直接是YES的，還要看看mx是否大于0

#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL;#include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int maxn = 1000000 + 20; int att[maxn]; int fre[maxn]; int wait[maxn]; void work() {int HP, hurt;int MYHP, m;scanf("%d%d%d%d", &HP, &hurt, &MYHP, &m);int mx = -inf;for (int i = 1; i <= m; ++i) {scanf("%d%d%d", &att[i], &fre[i], &wait[i]);mx = max(mx, att[i]);}int need = MYHP / hurt + ((MYHP % hurt) > 0);for (int i = 1; i <= m; ++i) {int dis = wait[i] - fre[i];if (dis == 0 && att[i] == 0) continue;if (dis == 0 && att[i] != 0) {printf("YES\n");return;}if (dis < 0 && mx != 0) {printf("YES\n");return;}if (dis < 0 && mx == 0) {continue;}int how = need / dis + ((need % dis) > 0); // printf("%d*****\n", how);int cut = (how - 1) * att[i] + mx;if (cut >= HP) {printf("YES\n");return;} // cout << cut << endl; }printf("NO\n");return; }int main() { #ifdef localfreopen("data.txt","r",stdin); #endifint t;scanf("%d", &t);while (t--) work();return 0; } View Code

?

不要看題解了，看這個數據

1
100 1
20 3
49 0 17
50 0 100
1 0 1

我的wa

轉載于:https://www.cnblogs.com/liuweimingcprogram/p/6065254.html

總結

以上是生活随笔為你收集整理的1191: 冰法斗神龙 暴力枚举的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。