线段树和单调队列优化DP---POJ2373解题报告
在长为L(<=1000000)的草地（可看成线段）上装喷水头，喷射是以这个喷水头为中心，喷水头的喷洒半径是可调节的，
调节范围为[a,b]。要求草地的每个点被且只被一个喷水头覆盖，并且有些连续区间必须被某一个喷水头覆盖，
而不能由多个喷头分段完全覆盖，求喷水头的最小数目。
很容易想到，这可以用dp解决，定义dp[i]为覆盖[0,i]区间所需的的最小喷头数，
则dp[0]=0,dp[i]=min{dp[i-2*b]....dp[i-2*a]}；因为喷头是向两边喷洒的，所以一个喷头覆盖的区间长度一定是偶数，
又由于题目要求喷头不能喷洒到[0,L]以外的区域，所以0开始的长度为奇数的子区间[0,L’]是不能被完全覆盖的。
还有一个问题是，某些连续区间必须被某一个喷水头覆盖这个限制该如何解决。我们可以这样想，
如果[s,e]这个区间只能被一个喷头覆盖，则[0,M](s<M<e)这一段子区间将不允许被完全覆盖，
因为如果[0,M]被完全覆盖会导致[s,e]区间被分割，所以我们可以对所以的[s,e]做上标记，
一种比较方便编码的方法是直接在dp这个数组上用一个特殊的值标记。我的做法是这样的：
代码：
代码：
#include<cstdio>#define L 1001000int a,b,n,l,inf,dp[L],queue[L],head,tail,size;void insert(int idx){ tail++; while(head<tail && dp[queue[tail-1]]>dp[idx]) tail--; queue[tail]=idx; while(idx-queue[head]>=size) head++;}int dpro(void){ if(b<1) return -1; dp[0]=0; size=2*b+1; head=0; tail=-1; for(int i=a; i<=b; i++) if(dp[2*i]<=inf) dp[2*i]=1; int seg = 2*b-2*a; for(int i=0; i<=seg; i+=2) insert(i); for(int i=2*b; i<=l; i+=2) { if(i-a*2>seg) insert(i-a*2); while(i-queue[head]>=size) head++; if (dp[i]<=inf) dp[i]=dp[queue[head]]+1; } if(dp[l]>=inf) return -1; else return dp[l];}int main(){ while (scanf("%d%d", &n, &l)!=EOF) { scanf("%d%d", &a, &b); inf = (l/a)+9; for(int i=0; i<=l; i++) dp[i]=inf; for(int i=0; i<n; i++) { int s, e; scanf("%d%d", &s, &e); for(int j=s+1; j<e; j++) dp[j] = inf+1; } if(l&1==1) printf("-1\n"); else printf("%d\n", dpro()); } return 0;}
