Speedrun (AOJ2591)
公式解説見ればOK
こういう系結構出るから気をつけないとね
セーブしうる所を全部持って(実装上Nも入れとくと楽)lower_boundで毎回探して30個くらい回せばOK.実装苦手なのでこういうのですら詰まるんだよなあ・・・
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define all(c) c.begin(),c.end() #define pb push_back #define fs first #define sc second #define show(x) cout << #x << " = " << x << endl #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) using namespace std; int main(){ while(true){ int N; double p[100000],dp[100001]={},inf=1e20; vector<int> vc; cin>>N; if(N==0) break; rep(i,N) cin>>p[i]; rep(i,N) if(p[i]!=1) vc.pb(i); vc.pb(N); rep(i,N+1) dp[i]=inf; dp[N]=0; for(int i=N-1;i>=0;i--){ int id=lower_bound(all(vc),i+1)-vc.begin(); double ex=0; int pre=i; for(int j=id,cnt=0;j<vc.size()&&cnt<30;j++,cnt++){ int v=vc[j]; ex=(ex+1)/p[pre]+(v-pre-1); chmin(dp[i],ex+(v==N?0:1)+dp[v]); pre=v; } } printf("%.12f\n",dp[0]); } }