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]);
	}
}