codeforces 1443 problem D
题目链接
题目大意：给你一个长度为n序列，你可以进行无数次操作，让前k个数减一或让后k个数减一，1<=k<=n,问是否能把这整个序列变为0序列，
（我是傻逼，没有初始化，太菜了，比赛的时候没有做出来QAQ ）
写题时要找好清晰的思路
8
252 210 750 818 640 868 700 777
首先可以确定，如果一个数能被减小，他能减少的数值一定不会超过他之前能被减少的数值
比如上面那个例子，750绝对不可能变成比540还小的数，如果继续变的话第二个数就会变成负数
第二，他被减完后的数一定是要大于前面的数的，不然从后往前减的时候，前面那个数就不会变成0
比如818->608之后,640->430，在从后往前筛时608这个数是一定不能变为0的，所以640只能变为608
所以我们发现接下来的数最多也就只能减32的所以能被减的数是不断变小的
如果经过从前往后筛和从后往前筛都不能让这个序列变为0，那么这个序列就是不好的，否则就是好的

#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
const int maxn=2e6+10;
#define inf 9999969
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define fep(i,a,b) for(int i=b;i>=a;--i)
#define scf(x) scanf("%lld",&x)
#define prf(x) printf("%lld\n",x)
#define deprf(x) printf("[%lld]\n",x)
#define mymset(x,y) memset(x,y,sizeof(x))
const int mod=9901;
using namespace std;
ll a[maxn];
int main()
{ 
	ll t,n;
	scf(t);
	while(t--)
	{ 
		scf(n);
		rep(i,1,n)scf(a[i]);
		ll lala=a[1];//这个lala存的是改变前和改变后的最小差值 
		a[0]=0,a[n+1]=0;
		rep(i,1,n)
		{ 
			ll p=a[i];
			if(a[i])a[i]=max(max(0LL,min(a[i-1],a[i])),a[i]-lala);//改变后不能超过前面的数
																//且不能小于0
			else break;									//如果能减最大只能减前面的最小差值
			if(p==a[i])break;//如果这个数没有发生改变证明接下来的数也就不能被减了
			lala=min(lala,p-a[i]);//更新最小差值
		}
		
		lala=a[n];
		fep(i,1,n)//从后往前跟从前往后是一样的
		{ 
			ll  p=a[i];
			if(a[i])a[i]=max(max(0LL,min(a[i+1],a[i])),a[i]-lala);
			else break;
			if(p==a[i])break;
			lala=min(lala,p-a[i]);
		}
		int f=0;//答案标记
		rep(i,1,n)if(a[i])f=1;//查看是否有数不为0
		if(f)printf("NO\n");
		else printf("YES\n");
	}
	return 0;
}