在長為L(<=1000000)的草地（可看成線段）上裝噴水頭，噴射是以這個噴水頭為中心，噴水頭的噴灑半徑是可調(diào)節(jié)的調(diào)節(jié)范圍為[a,b]。要求草地的每個點被且只被一個噴水頭覆蓋，并且有些連續(xù)區(qū)間必須被某一個噴水頭覆蓋，而不能由多個噴頭分段完全覆蓋，求噴水頭的最小數(shù)目。

解題思路：這道題是單調(diào)隊列優(yōu)化dp，狀態(tài)方程很容易想到，關(guān)鍵是優(yōu)化問題，那么我們就需要維護一個隊列放dp[j]，使得隊列中的元素j至少比i要小2 *a, 而同時隊頭的元素j不能比i小2*b以上，關(guān)鍵在于哪些元素應(yīng)該入隊，哪些不應(yīng)該入隊。

自己寫沒寫出來，盜了別人的代碼。。

參考博客：http://blog.csdn.net/sunny606/article/details/7854362

#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; }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++) insert(i);for(int i=2*b; i<=l; i+=2){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; }

總結(jié)

以上是生活随笔為你收集整理的poj 2373(单调队列优化dp)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。