またしょうもないミスで上位を逃す…。
http://codeforces.com/contest/965/problem/D
問題
Wの幅の川がある。
蛙は1回で最大L以下の距離ジャンプできる。
川の途中いくつか石があり、1つの石ごとに蛙が1体乗れる。1度蛙が乗った石は以後他の蛙は乗れない。
各位置の石の数が与えられたとき、川を渡り切れる蛙は最大何体か。
解法
各位置xに石がA[x]個あるとき、[(x-L),(x-1)]の範囲にいる蛙は最大A[x]個までこの位置に止まることができる。
当然ながらできるだけ手前にいる蛙をこの石に乗せた方が、総数を最大化できる。
よって各位置の蛙の数をmap等で管理し、範囲内で手前にいる順で蛙を位置xに動かそう。
int W,L; ll A[101010]; ll num[101010]; void solve() { int i,j,k,l,r,x,y; string s; cin>>W>>L; for(i=1;i<W;i++) cin>>A[i]; A[W]=1LL<<30; num[0]=1LL<<30; int pre=0; for(i=1;i<=W;i++) { if(pre<i-L) pre++; while(pre<i && A[i]>0) { x=min(num[pre],A[i]); num[pre]-=x; A[i]-=x; num[i]+=x; if(num[pre]==0) pre++; } } cout<<num[W]<<endl; }
まとめ
まぁこれはすんなり。