【BZOJ4476】[Jsoi2015]送禮物

Description

JYY和CX的結(jié)婚紀(jì)念日即將到來，JYY來到萌萌開的禮品店選購紀(jì)念禮物。
萌萌的禮品店很神奇，所有出售的禮物都按照特定的順序都排成一列，而且相鄰的禮物之間有一種神秘的美感。于是，JYY決定從中挑選連續(xù)的一些禮物，但究竟選哪些呢？
【問題描述】
假設(shè)禮品店一共有N件禮物排成一列，每件禮物都有它的美觀度。排在第i1< =i< =N個(gè)位置的禮物美觀度為正整數(shù)Ai,。JYY決定選出其中連續(xù)的一段，即編號(hào)為禮物i,i+1,…,j-1,j的禮物。選出這些禮物的美觀程度定義為
(M（i,j)-m(i,j))/(j-i+k)
其中M(i,j)表示max{Ai,Ai+1....Aj}，m(i,j)表示min{Ai,Ai+1....Aj}，K為給定的正整數(shù)。
由于不能顯得太小氣，所以JYY所選禮物的件數(shù)最少為L件；同時(shí)，選得太多也不好拿，因此禮物最多選R件。JYY應(yīng)該如何選擇，才能得到最大的美觀程度？由于禮物實(shí)在太多挑花眼，JYY打算把這個(gè)問題交給會(huì)編程的你。

Input

本題每個(gè)測試點(diǎn)有多組數(shù)據(jù)。輸入第一行包含一個(gè)正整數(shù)T(T< =10)，表示有T組數(shù)據(jù)。
每組數(shù)據(jù)包含兩行，第一行四個(gè)非負(fù)整數(shù)N,K,L,R(2< =L< =R< =N。第二行包含N個(gè)正整數(shù)，依次表示A1,A2....An,(Ai< =10^8),N,K< = 50,000

Output

輸出T行，每行一個(gè)非負(fù)實(shí)數(shù)，依次對(duì)應(yīng)每組數(shù)據(jù)的答案，數(shù)據(jù)保證答案不會(huì)超過10^3。輸出四舍五入保留4位小數(shù)。

Sample Input

1
5 1 2 4
1 2 3 4 5

Sample Output

0.7500

題解：顯然先分?jǐn)?shù)規(guī)劃，然后根據(jù)貪心，選出來的區(qū)間的最大和最小值一定是在兩端的，設(shè)最大值為v[i],最小值為v[j]，所以式子就變成：

v[i]-v[j]-(i-j+k)*mid>0或v[i]-v[j]-(j-i+k)*mid>0

然后分開討論，第一個(gè)變成求(v[i]-i*mid)-(v[j]-j*mid)的最大值，第二個(gè)變成求(v[i]+i*mid)-(v[j]+j*mid)的最大值，題解說可以用單調(diào)隊(duì)列搞定，但是我比較懶，直接用的RMQ。

但是感覺不對(duì)？當(dāng)最大最小值的距離<L時(shí)，我們也要將長度視為L，即v[i]-v[j]-(L-1+k)*mid>0，同理，求v[i]-v[j]的最大值即可，依舊RMQ。

所以。。。所以RMQ比單調(diào)隊(duì)列慢。。。所以又光榮的變成status倒數(shù)第一，并且時(shí)間也很吉利~

（時(shí)限30s）

#include <cstdio> #include <cstring> #include <iostream> using namespace std; const double eps=1e-7; const int maxn=100010; int n,K,L,R,h,t; int v[maxn],Log[maxn]; double f1[18][maxn],f2[18][maxn]; int f[18][maxn]; int rd() {int ret=0,f=1; char gc=getchar();while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();return ret*f; } double q1(int l,int r) {int k=Log[r-l+1];return min(f1[k][l],f1[k][r-(1<<k)+1]); } double q2(int l,int r) {int k=Log[r-l+1];return min(f2[k][l],f2[k][r-(1<<k)+1]); } int q(int l,int r) {int k=Log[r-l+1];return min(f[k][l],f[k][r-(1<<k)+1]); } bool solve(double sta) {int i,j;double ret=-99999999.9999;for(i=1;i<=n;i++) f1[0][i]=v[i]-sta*i,f2[0][i]=v[i]+sta*i;for(j=1;(1<<j)<=n;j++) for(i=1;i+(1<<j)-1<=n;i++)f1[j][i]=min(f1[j-1][i],f1[j-1][i+(1<<j-1)]),f2[j][i]=min(f2[j-1][i],f2[j-1][i+(1<<j-1)]);for(i=1;i<=n;i++){if(i>=L) ret=max(ret,f1[0][i]-q1(max(1,i-R+1),i-L+1));if(i<=n-L+1) ret=max(ret,f2[0][i]-q2(i+L-1,min(n,i+R-1)));}for(i=1;i<=n;i++){ret=max(ret,v[i]-q(max(1,i-L+1),min(n,i+L-1))-sta*(L-1));}return ret>=K*sta; } void work() {n=rd(),K=rd(),L=rd(),R=rd();int i,j;for(i=1;i<=n;i++) f[0][i]=v[i]=rd();for(i=2;i<=n;i++) Log[i]=Log[i>>1]+1;for(j=1;(1<<j)<=n;j++) for(i=1;i+(1<<j)-1<=n;i++) f[j][i]=min(f[j-1][i],f[j-1][i+(1<<j-1)]);double l=0,r=1000,mid;while(r-l>eps){mid=(l+r)/2;if(solve(mid)) l=mid;else r=mid;}printf("%.4lf\n",l);return ; } int main() {int T=rd();while(T--) work();return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/CQzhangyu/p/7246831.html

總結(jié)

以上是生活随笔為你收集整理的【BZOJ4476】[Jsoi2015]送礼物 分数规划+RMQ的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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