あと1分速く解きたかったね。
http://yukicoder.me/problems/no/484
問題
1~N番のN個の木が順に左右に並んでいる。
タヌキは時刻0で任意の位置にいることができる。
また、時間1をかけて隣の木に移動することができる。
i番の木には、時刻A[i]に実がなることがわかっている。
タヌキはすべての木を回り、すべての木の実を収穫したい。(収穫にかかる時間は無視できる)
最適な順で移動した際にかかる最短の時間を求めよ。
解法
遠くにある木の実を回収しようとする場合、その途中にある(すでに生っている)実は回収できる。
そこで、左右それぞれもっとも遠い場所で、残りどこまで収穫しなければならないかを考える。
f(L,R,side)を以下のように定義する。
- f(L,R,left) := あと区間[L,R]の木の実を収穫しなければいけない状態で、ちょうどL番の実を収穫した状態になる最短時刻
- f(L,R,right) := あと区間[L,R]の木の実を収穫しなければいけない状態で、ちょうどR番の実を収穫した状態になる最短時刻
それぞれ、f(1,N,left) = A[1]、f(1,N,right) = A[N]を初期値とし、f(L-1,R,left)およびf(L,R+1,right)からf(L,R,left)、f(L,R,right)を更新していこう。
最終的にmin_x(f(x,x,left))が解。(L=Rの場合残る実は1つなので第3引数はleftでもrightでも同じ)
int N; ll A[2020]; ll memo[2020][2020][2]; ll hoge(int L,int R,int S) { if(memo[L][R][S]>=0) return memo[L][R][S]; ll& ret=memo[L][R][S]; ret=1LL<<60; if(L==0 && R==N-1) { if(S==0) ret=A[0]; else ret=A[N-1]; } else { if(S==0) { if(L) ret=min(ret,hoge(L-1,R,0)+1); if(R<N-1) ret=min(ret,hoge(L,R+1,1)+(R+1-L)); ret=max(ret,A[L]); } else { if(L) ret=min(ret,hoge(L-1,R,0)+(R-(L-1))); if(R<N-1) ret=min(ret,hoge(L,R+1,1)+1); ret=max(ret,A[R]); } } return ret; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) cin>>A[i]; MINUS(memo); ll mi=1LL<<50; FOR(i,N) mi=min(mi,hoge(i,i,0)); cout<<mi<<endl; }
まとめ
面白かったです。
なんか二分探索解を書いてる人が多かったね(最小値を求める問題なので気持ちはわかる)。