正題

題目鏈接:https://jzoj.net/senior/#contest/show/3011/2

---

題目大意

$n+1$個連續的地方，每個地方有$(a,b,c)$。

從$0$開始，每次往前選擇一個不超過$L$的位置，跳到那里并選擇中間不包括起點的位置中$c$最大的地方獲取這個位置的$a,b$。

最后要求$a$的值和$b$的值比值最大。

---

解題思路

顯然的0/1分數規劃問題，二分答案$mid$，把價值變為$a?b?mid$，然后求價值最大。

考慮$dp$，先預處理出每個位置的$c_i$能影響到的位置(前面的最近一個比它大的$c$)。

然后$dp$，$f_i$表示走到$i$時最大價值。

枚舉一個$i$,我們現在要計算$f_i$，然后定義$w_j$表示從$j$跳到$i$時需要戰斗的地方的價值。

然后用一顆線段樹維護$f$的區間最大值和$f+w$的區間最大值，之后我們每次單點修改$f$，區間修改$w$即可。

時間復雜度$O(100n\log n)$（這里進行了$100$次二分）。

---

$code$

#pragma GCC optimize(2) %:pragma GCC optimize(3) %:pragma GCC optimize("Ofast") %:pragma GCC optimize("inline") #include<cstdio> #include<cstring> #include<algorithm> #define lowbit(x) (x&-x) using namespace std; const int N=3e4+10; const double eps=1e-7; int n,l,c[N],h[N],last[N]; double a[N],b[N],f[N],w[N]; struct Tree_Array{int t[N];void Change(int x,int val){while(x<=n){t[x]=val;x+=lowbit(x);}}int Ask(int x){int ans=0;while(x){ans=max(ans,t[x]);x-=lowbit(x);}return ans;} }Ta; struct Seq_Tree{double f[N*4],w[N*4],lazy[N*4];void ReBuild(){for(int i=0;i<4*N;i++)f[i]=w[i]=-1e9,lazy[i]=0;return;}void Merge(int x){f[x]=max(f[x*2],f[x*2+1]);w[x]=max(w[x*2],w[x*2+1]);return;}void Downdata(int x){if(lazy[x]==0) return;w[x*2]=f[x*2]+lazy[x];w[x*2+1]=f[x*2+1]+lazy[x];lazy[x*2]=lazy[x*2+1]=lazy[x];lazy[x]=0;return;}void ChangeF(int x,int pos,int L,int R,double val){if(L==R){f[x]=val;return;}Downdata(x);int mid=(L+R)>>1;if(pos<=mid) ChangeF(x*2,pos,L,mid,val);else ChangeF(x*2+1,pos,mid+1,R,val);Merge(x);return;}void ChangeZ(int x,int l,int r,int L,int R,double val){if(L==l&&R==r){lazy[x]=val;w[x]=f[x]+val;return;}Downdata(x);int mid=(L+R)/2;if(r<=mid) ChangeZ(x*2,l,r,L,mid,val);else if(l>mid) ChangeZ(x*2+1,l,r,mid+1,R,val);else ChangeZ(x*2,l,mid,L,mid,val),ChangeZ(x*2+1,mid+1,r,mid+1,R,val);Merge(x);return;}double Ask(int x,int l,int r,int L,int R){if(L==l&&R==r)return w[x];Downdata(x);int mid=(L+R)/2;if(r<=mid) return Ask(x*2,l,r,L,mid);if(l>mid) return Ask(x*2+1,l,r,mid+1,R);return max(Ask(x*2,l,mid,L,mid),Ask(x*2+1,mid+1,r,mid+1,R));} }T; bool check(double x){for(int i=1;i<=n;i++)w[i]=a[i]-b[i]*x;T.ReBuild();T.ChangeF(1,0,0,n,0);for(int i=1;i<=n;i++){T.ChangeZ(1,last[i],i-1,0,n,w[i]);f[i]=T.Ask(1,max(0,i-l),i-1,0,n);T.ChangeF(1,i,0,n,f[i]);}return f[n]>=0; } int main() {scanf("%d%d",&n,&l);for(int i=1;i<=n;i++){scanf("%lf%lf%d",&a[i],&b[i],&h[i]);c[i]=h[i];}sort(c+1,c+1+n);int m=unique(c+1,c+1+n)-c-1;for(int i=1;i<=n;i++){h[i]=m-(lower_bound(c+1,c+1+m,h[i])-c)+1;last[i]=Ta.Ask(h[i]-1);Ta.Change(h[i],i);}double l=0,r=1000000;for(int i=1;i<=100;i++){double mid=(l+r)/2.0;if(check(mid)) l=mid;else r=mid;}double ans=(l+r)/2;int loc=0;while(ans>10) ans/=10,loc++;while(ans<1) ans*=10,loc--;printf("%.9lfe",ans);if(loc>=0) printf("+%03d",loc);else printf("%04d",loc);return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的jzoj4017-逃跑【0/1分数规划,线段树,dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。