跳柱子

#include<bits/stdc++.h>
#define MP make_pair
#define PB emplace_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&& ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=1e3+10;
int T,n,k,i,j,h[N];
bool dp[N][2];
int main(){
	for (read(T);T--;){
		read(n),read(k);
		for (i=1;i<=n;++i) read(h[i]),dp[i][0]=dp[i][1]=0;
		dp[1][0]=1;
		for (i=2;i<=n;++i){
			for (j=1;j<=i;++j)if(i-j>=1 && i-j<=k){
				if (h[j]>=h[i]){
					dp[i][0]|=dp[j][0];
					dp[i][1]|=dp[j][1];
				}
				dp[i][1]|=dp[j][0];
			}
		}
		if (dp[n][0] || dp[n][1]) puts("YES");
		else puts("NO");
	}
	return 0;
}

积木

#include<bits/stdc++.h>
#define MP make_pair
#define PB emplace_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&& ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=1e5+10;
int T,n,i;
ll m,h[N];
int main(){
	for (read(T);T--;){
		read(n),read(m);
		for (i=0;i<n;++i) read(h[i]);
		bool flag=0;
		for (i=0;i<n;++i){
			if (h[i]>i) m+=h[i]-i;
			else{
				if (i-h[i]>m){
					flag=1;
					break;
				}
				else m-=i-h[i];
			}
		} 
		puts(flag?"NO":"YES");
	}
	return 0;
}