CF1469C

DDF_ · 2025-09-02 21:50:05 · 题解

题解

简单 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。

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

代码

#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;
}