1007 Climb Stairs (greedy | C thinking)

Intention

Xiao Ming wants to climb a building with n floors, and each floor has a monster with a life value of hi.This monster can only be destroyed when Xiao Ming's attack power a>= health h.If Xiao Ming destroys this monster, he will absorb his HP and convert it into his own attack power.Initially, Xiao Ming is on the 0th floor and has an attack power of a0.

Xiao Ming has two ways of acting

One is to move up i cells, i<=k; the other is to go down 1 cell.A floor cannot be climbed twice

Now Xiaoming wants to climb to the top of the building and destroy all the monsters, ask Xiaoming if he can do it.

Thoughts

Segmented processing.Since the title requires that all monsters must be beaten, the skipped monsters have to go back to defeat them.We need to find a right endpoint r from the current position x, so that the monsters in this section can be defeated in the order of r, r-1, r-2, x.It is not difficult to see that it is not worse when r is smaller.

greedy.Greed from back to front.The farthest can be from i + k - 1 (equivalent to Xiaoming jumping to i + k - 1 and then going down, and when you reach i, you can still jump to the i + k layer) Start greedy, and reset the value if you are not greedy.(Skip this hard bone for a while, and process the current a[i] hard bone first), reduce the scope of greed, the purpose is to make value >= a[i], if it is not reached, output NO

#includetypedef long long ll;using namespace std;int n,w,k;void solve(){cin >> n >> w >> k;std::vector a(n + 1);for (int i = 1; i <= n; i++ ) cin >> a[i];for (int i = 1; i <= n; i++ ) {if(a[i] <= w) {w += a[i];} else {bool ok = false;int j = min(n, i + k - 1);int value = w;for (int z = j; z >= i; z -- ) {if(a[z] <= value) {value += a[z];if(z == i) {ok = true;}} else {value = w;j = z;// i = j;;}}if(ok) {i = j;w = value;} else {cout << "NO\n";return;}}}cout << "YES\n";}int main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t;cin >> t;while(t--) {solve();}return 0;}