本文共 1063 字，大约阅读时间需要 3 分钟。
思路：
设dp[i]为覆盖i所用的最小数量，那么dp[i] = min(dp[k] + 1)，其中i - 2b <= k <= i -2a，所以可以手动开一个单调递增的队列，队首元素就是k。
初始状态为dp[0] = 0，注意喷水覆盖的范围是偶数且不重叠，所以插入队列的必是偶数。有牛的地方不能作为边界，所以这些地方都要排除，可以用vis标记或者其他方法。
代码：
#include#include #include #include #include #include #include #include #include #include #include #include const int N = 1000000+5;const int INF = 0x3f3f3f3f;using namespace std;int dp[N],q[N]; //单调递增队列:队首是当前dp最小的int main() { int n,l,a,b,L,R; scanf("%d%d%d%d",&n,&l,&a,&b); memset(dp,INF,sizeof(dp)); for(int i = 0;i < n;i++){ scanf("%d%d",&L,&R); for(int j = L + 1;j <= R - 1;j++){ dp[j] = INF + 1; } } int head = 0,tail = 0; dp[0] = 0; for(int i = 2*a;i <= l;i+= 2){ while(head < tail && dp[q[tail - 1]] >= dp[i - 2*a]) tail--; q[tail++] = i - 2*a; while(head < tail && q[head] < i - 2*b) head++; //i - 2*b <= j <= i - 2*a if(dp[i] <= INF) dp[i] = dp[q[head]] + 1; } if(dp[l] < INF) printf("%d\n",dp[l]); else printf("-1\n"); return 0;}
转载于:https://www.cnblogs.com/KirinSB/p/9408780.html