Building a Fence (递推)

题目 参考

题意：给定n个栅栏，宽度为1，高度为 h i h_i hi​，现在要在这n个栅栏摆放高度为k的木板。要求有：

1、木板摆放最低高度为 h i h_i hi​，即栅栏的高度，最高高度为 h i + k − 1 h_i+k-1 hi​+k−1，即不能离地面高度超过k。 2、相邻的木板至少有1个单位的长度衔接。 3、首尾木板要贴近栅栏，不能悬空（即高度只能为 h i h_i hi​）。

现在给定这些栅栏，问能否满足上述要求。

题解：当前木板的摆放高度范围，和自身所在栅栏高度 h i h_i hi​，和上一个木板的摆放位置有关。因此，我们可以从左到右，计算每个木板的最低范围和最高范围。当相邻木板不能衔接时，说明不能满足要求。

#include
using namespace std;
#define ll long long
const int maxn = 200010;

int n, k;
int h[maxn];

int main() {
	
	int t;
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d", &n, &k);
		for (int i = 0; i