[贪心]Climb Stairs 2022杭电多校第4场 1007

Problem Description

DLee came to a new level. What is waiting for him is a tall building with nn floors, with a monster on each stair, the ii-th of which has health point a_iai​.

DLee starts from the ground(which can be regarded as the 0-th floor), with a base attacking point a_0a0​. He can choose to jump 1,2,\dots,k1,2,…,k floors up or walk 11 floor down, but he cannot go to floors whose monster has a health point strictly greater than his attacking point, nor can he go to floors which had been visited. Once he comes and defeats a monster he can absorb his health point and add it to his attacking point.

Note that DLee should always be on floors {0,1,2,3,\dots,n}0,1,2,3,…,n.

Now DLee asks you whether it is possible to defeat all the monsters and pass the level.

Input

There are TT test cases.

In each test case, the first line contains three integers: n,a_0,k(1\leq n,k\leq 10^5,1\leq a_0\leq 10^9)n,a0​,k(1≤n,k≤105,1≤a0​≤109), representing the number of floors, base attacking point, and the maximum number of floors that DLee can jump.

The second line contains nn integers a_1,\dots,a_n(1\leq a_i\leq 10^9)a1​,…,an​(1≤ai​≤109), representing the health point of each monster.

The sum of nn does not exceed 10^6106.

Output

For each test case, output "YES" or "NO" to show whether it's possible to defeat all monsters.

Sample Input

4

6 1 4

2 2 1 1 9 3

4 2 2

2 3 8 1

3 1 2

3 1 2

7 2 3

4 3 2 7 20 20 20

Sample Output

YES

YES

NO

NO

题意： 有一座n层的塔，每层都有一只怪物，它们的血量分别为hp[i]，现在你有m点攻击力，处于第0层，每次操作可以选择向上跳小于等于k的层数，或者向下走1层，能到达相应层数的前提是必须能够击杀那层的怪物，并且击杀怪物后你的攻击力会增加hp[i]点，而且走过的层不能再走了，问能否最终击败所有怪物。

分析： 由于向下只能走一层，所以当向上跳跃时，一定要把下面的怪物清光，否则之后就过不去了，另外有可能向上走时遇到了一个比较强的怪物，这时候可以先跳过它，等击败了上面的怪物增强实力后再下来打它，具体跳到上面的哪一层是有点贪心思想的，应该跳到刚好能从那层连续杀下去的位置，这样一定不会比其他情况更差，于是这道题目大体思路就有了，可以枚举向上跳几层，找到第一个能杀回去的层数，然后就可以更新位置信息了，如此往复直至到达最高层，这也就意味着击败了全部的怪物。

不过枚举跳几层时需要知道能否从该层杀回去，这个信息处理起来比较巧妙，用到了dp的思想，设low_at[i]为从第i层杀回去所需要的最少攻击力，首先这个值一定要大于等于hp[i]，不然第一个怪都打不死，打败了第i层的怪物后只需要再打败第i层以下的怪就可以了，这需要的攻击力就是low_at[i-1]，并且打完第i层怪后攻击力还会上升hp[i]点，所以只需要max(hp[i], low_at[i-1]-hp[i])的攻击力就可以从第i层杀回去。

这样这道题目就解决了，具体细节都在代码中，总时间复杂度为O(n)。

具体代码如下：

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
 
int hp[100005], s[100005];
 
signed main()
{
	int T;
	cin >> T;
	while(T--){
		int n, m, k;
		scanf("%d%d%d", &n, &m, &k);
		for(int i = 1; i <= n; i++){
			scanf("%d", &hp[i]);
			s[i] = s[i-1]+hp[i];
		}
		int now = 0, at = m;//当前层数以及攻击力
		bool end = false;
		int low_i = 1;
		while(true){
			int low_at = 0;//跳到最优层所需攻击力 
			bool flag = false;
			for(int i = low_i; i <= k && now+i <= n; i++){
				int to = now+i;
				low_at = max(low_at-hp[to], hp[to]); 
				if(at >= low_at){
					at += s[to]-s[now+low_i-1];
					now += low_i;
					low_i = i-low_i+1;
					flag = true;
					if(to == n)
						end = true;
					break; 
				}
			}
			if(!flag || end) break;
		} 
		if(end) puts("YES");
		else puts("NO");
	} 
    return 0;
}