CF1469C

题解

简单 DP。

可以发现栅栏摆放的地方是一段区间，所以可以设

f_{i,0}

为第

i

个栅栏底端的最低高度，

f_{i,1}

为最高高度。

那么

f_{1,0}=f_{1,1}=h_{1}

。

容易想到

f_{i}

会被

f_{i-1}

和

h_{i}

约束。

求

i

最高高度，我们在上一个最高的基础上尽量往上搭，则有

f_{i,1}=\max(f_{i-1,1}+k-1,h_{i}+k-1)

。

求最低，在上一个最低的基础上尽量往低放，则有

f_{i,0}=\min(f_{i-1,0}-k+1,h_{i})

。

然后我们去看是否有与题目约束矛盾的地方。

首先，

f_{n,0}

必须为

h_{n}

。

其次，对于

i \in [1,n]

，

f_{i,1} \ge h_{i}

且

f_{i,0} \le h_{i}+k-1

。

判断这两个条件是否都满足即可。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int t;
int n,k;
int h[N],f[N][2];
void solve() {
	memset(f,0,sizeof f);
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) scanf("%d",&h[i]);
	f[1][0]=f[1][1]=h[1];
	for(int i=2;i<=n;i++) {
		f[i][1]=min(f[i-1][1],h[i])+k-1;
		f[i][0]=max(f[i-1][0]-k+1,h[i]);
		if(f[i][1]<h[i]||f[i][0]>h[i]+k-1) {puts("NO");return;}
	}
	if(f[n][0]==h[n]) puts("YES");
	else puts("NO");
	return;
}
int main() {
	scanf("%d",&t);
	while(t--) solve();
	return 0;
}

文章操作

题解

代码

相关推荐

评论

CF1469C