在長為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這個數組上用一個特殊的值標記。我的做法是這樣的：
[cpp]
dp[0]=0;
for(int i=1; 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;//用inf+1表示不允許覆蓋
}
完整代碼：
[cpp]
#include<cstdio>
#include<cstring>
#define L 1001000
int a,b,n,l,inf,dp[L];
int dpro(void)
{
if(b<1) return -1;
dp[0]=0;
for(int i=2; i<=l; i+=2)
{
if (dp[i]<=inf) {
int min = inf;
for(int j=a; j<=b; j++) {
int idx = i-2*j;
if(idx<0) break;
if ( min>dp[idx] ) min=dp[idx];
}
dp[i]=min+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", dpro());
}
return 0;
}
從上面的程序中我們看到，在最壞的情況下，時間復雜度是O(L^2)，而L的范圍可達一百萬，
所以在極端的數據下，這個程序是會超時的，所以我們需要對這個程序做一點優化。
在dp過程中的第二層for循環的作用是找出[i-2*b,i-2*a]這段區間的最小值，
這個查找一段區間的最小值的操作可以用線段樹來優化，優化後的時間復雜度是O(LlgL)。
代碼：
[cpp]
#include<cstdio>
#include<cstring>
#define L 1001000
int a,b,n,l,inf,dp[L];
int tree[4*L];
void updata(int *p, int rt, int l, int r,int pos, int k)
{
if (l==r) {
p[rt]=k;
return ;
}
int mid=(l+r)>>1;
if (pos<=mid) updata(p,rt<<1, l, mid, pos, k);
else updata(p, rt<<1|1, mid+1, r, pos, k);
int lv=p[rt<<1];
int rv=p[rt<<1|1];
p[rt]=lv<rv?lv:rv;
}
int query(int *p,int rt, int l,int r, int s, int e)
{
if(l==s && e==r) return p[rt];
int mid = (l+r)>>1;
if(e<=mid) return query(p, rt<<1, l, mid, s, e);
if(s>mid) return query(p, rt<<1|1, mid+1, r, s, e);
int lv=query(p,rt<<1, l, mid, s,mid);
int rv=query(p,rt<<1|1, mid+1, r, mid+1, e);
return lv<rv?lv:rv;
}
int dpro(void)
{
if(b<1) return -1;
dp[0]=0;
for(int j=0; j<4*L; j++) tree[j]=L*2;
for(int j=a; j<=b; j++){
if(dp[2*j]<=inf) dp[0+2*j] = dp[0]+1;
updata(tree,1, 1, l ,j,dp[2*j]);
}
for(int i=2*b+2; i<=l; i+=2)
{
int min;
int pos = (i>>1);
min = query(tree, 1, 1, l, pos-b, pos-a);
if (dp[i]<=inf) {
//if(dp[i]>min+1)
dp[i]=min+1;
updata(tree,1,1,l,pos,dp[i]);
/*for(int j=a; j<=b; j++) {
int idx = i-2*j;
if(idx<0) break;
if ( dp[i]>dp[idx]+1 ) dp[i]=dp[idx]+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");
printf("%d\n", dpro());
}
return 0;
}
另一種更好的優化方法是用單調隊列優化：
代碼：
[cpp]
#include<cstdio>
#define L 1001000
int 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;
}
