信息科學(xué)技術(shù)學(xué)程序設(shè)計實 劉家 1信息科學(xué)技術(shù)學(xué)院《程序設(shè)計實習(xí)》劉家例題：灌溉草2在一片草有一條長為L(1<=L=,,，為偶的線段。hN(1=N<=100)頭奶都著場這條段草牛的活動圍是個開區(qū)(E都整同奶的動圍以有 。John要在這條線段上安裝噴水頭灌溉草場。每個噴水頭意調(diào)節(jié)，調(diào)節(jié)范圍是 B](1<=A<=B<=1000)，A,B都是整數(shù)。要線段上的每個整點恰好位于一個噴水頭的噴灑范圍每頭奶牛的活動范圍要位于一個噴水任何噴水頭的噴灑范圍不可越過線段的兩端(左端是0,右端是L34輸?shù)?行：整數(shù)N、L第2行：整數(shù)A、B第3到N+2行：每行兩個整數(shù)S、E0SEL表范圍的起點和終 段上的坐標(biāo)(即到線段起點的距離)輸出：最少需要安裝的多少個噴水頭；若沒有符合要求的噴，則輸出-1輸入樣2163

35從線段的起點向終點安裝噴水頭，令f(X)恰好覆蓋直線上的區(qū)間顯然，X應(yīng)滿足下列條X為偶

時，最少X所在位置不會出現(xiàn)奶牛，即X不屬于任何一個當(dāng)X2B時，存在Y[X- X-2A]且Y滿足上述三個條件，使f(XXf(X)=∝：X<f(X)=∝：X處可 f(X)=1+min{f(Y):Y[X-2B 之外}X>2B

!(FX2-A而且，X的點X隊列中可以出現(xiàn)坐標(biāo)小于X-2B的點。這樣的點若出現(xiàn)在隊頭，則直將其拋棄求出X點的F值后，將(X-2A+2,F(X-2A+2))放入隊列，為求F(X+2)作備隊列里只要存坐標(biāo)為偶數(shù)的點即#include<iostream>#include<cstring>#include<queue>usingnamespacestd;constintINFINITE=1<<31;constintMAXL= constintMAXN=1010;intF[MAXL];F[L]intcowThere[MAXL];//cowThere[i]為1表示點 intstructFxint intbooloperator<(constFx&a)constFx(intxx=0,intff=0):x(xx),f(ff){};在優(yōu)先隊列里，fpriority_queue<Fx>

returnf> int{cin>>N>>cin>>A>>A1B1;//A,Bfor(inti=0;i<N;++i)intcin>>s>>++cowThere[s+1//從s+1];}intinCows0//for(inti=0;i<=L;i++){//算出每個點是 F[i]=inCows+=cowThere[i]=inCows>}for(intiA;iBi2//if(!cowThere[i])F[i]=ifiB2A//在求F[i]的時候，要確保隊列里的點x，xi}for(inti=B+2;i<=L;i+=2)if(!cowThere[i]) Fxwhile(!qFx.empty())fx=if(fx.x<i-B}

if(!qFx.empty()F[i]=fx.f+}if(F[iA2INFINITE)//隊列中增加一個+1可達(dá)下個點的點qFx.push(Fx(iA+2,F[iA+2]))