本文共 2705 字，大约阅读时间需要 9 分钟。

$$DividingthePath$$

题目链接：

题目大意

在长为$L$的草地（可看成线段）上装喷水头，喷射是以这个喷水头为中心，喷水头的喷洒半径是可调节的，调节范围为$[a,b]$。要求草地的每个点被且只被一个喷水头覆盖，并且有些连续区间$[s,e]$必须被某一个喷水头覆盖而不能由多个喷头分段完全覆盖，求喷水头的最小数。

样例输入

2 81 26 73 6

样例输出

3

样例解释

沿着长度为$8$的草地的两头母牛。喷头的整数喷雾半径范围为$1..2$（即$1$或$2$）。一头牛喜欢$3-6$的范围，另一头喜欢$6-7$的范围。

需要三个洒水喷头：一个喷涂距离为$1$，喷涂距离为$1$，喷涂距离为$1$，喷涂距离为$1$，喷涂距离为$1$，喷涂距离为$1$，第二喷头浇水范围内的所有三叶草（如第二头奶牛） $3-6$）。最后一个喷水器浇灌了第一头牛（$6-7$）喜欢的所有三叶草。这是一个图表：

数据范围

$1<=N<=1000$

思路

这道题就是一道$dp$。

代码

#include
   
    #include
    
     #include
     
      using namespace std;int n, l, a, b, f[1000001], q[1000001], h, t, size, x, y;int main(){   	scanf("%d%d%d%d", &n, &l, &a, &b);//读入	if (l&1) {   return 0; printf("-1");}//判断是否可以完全覆盖	for (int i = 1; i <= n; i++)	{   		scanf("%d%d", &x, &y);//读入		for (int j = x + 1; j < y; j++)			f[j] = 1000000001;	}	f[0] = 0;//初始化	size = 2 * b - 2 * a;//初始化	for (int i = 2; i < 2 * a; i += 2)		f[i] = 1000000001;//初始化	for (int i = 2 * a; i <= l; i += 2)	{   		 while (h < t && f[q[t - 1]] >= f[i - 2 * a]) t--;//从后往前插入		 q[t++] = i - 2 * a;//入队		 while (i - 2 * a - q[h] > size) h++;//找可选区间		 if (f[i] <= 1000000000)		 	f[i] = f[q[h]] + 1;//dp	}	if (f[l] >= 1000000000) printf("-1");//做不到		else printf("%d", f[l]);//输出	return 0;}