AOJ 1306 Balloon Collecting
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1306
風船が時間tに位置pに落ちてくる。台車で3個まで運ぶことができて、距離1移動するのに台車は風船の数+1時間かかる。風船は途中で家に貯めることが出来る。
このとき、全ての風船を集めるのに必要な最小の移動距離か、集められなければ、最初に地面におっことすのは何番目の風船かを答えるというような問題。
動的計画法っぽいですが、漸化式を考えるのが面倒臭く感じたのでダイクストラしました。
キューに突っ込む情報に混乱しまくって、相当時間がかかりました。サンプルは親切な気がします。
typedef struct _state{ int ne,pos,time,len,bal; bool operator<(const _state&r)const{return len>r.len;}; }state; int p[41],t[41]; int vis[4][40]; main(){ int n; while(cin>>n,n){ rep(i,n)cin>>p[i]>>t[i]; memset(vis,0,sizeof(vis)); priority_queue<state> Q; int ans=INT_MAX/2; Q.push((state){0,0,0,0,0}); while(!Q.empty()){ state tt=Q.top();Q.pop(); //cout<<tt.ne<<' '<<tt.time<<' '<<tt.len<<' '<<tt.bal<<endl; int ne=tt.ne; if(tt.ne==n){ ans=min(ans,tt.len+tt.pos); continue; } if(vis[tt.bal][tt.ne])continue; vis[tt.bal][tt.ne]=1; if(tt.bal<=2 && tt.time+abs(p[tt.ne]-tt.pos)*(tt.bal+1)<=t[ne]) Q.push((state){ne+1,p[ne],t[ne],tt.len+abs(tt.pos-p[ne]),tt.bal+1}); if(tt.time+tt.pos*(tt.bal+1)+p[ne]<=t[ne]) Q.push((state){ne+1,p[ne],t[ne],tt.len+tt.pos+p[ne],1}); } if(ans<INT_MAX/2)cout<<"OK "<<ans<<endl; else{ cout<<"NG "; int i=0; for(;i<n;i++){ bool ok=false; rep(j,4) ok|=vis[j][i]; if(ok)continue; break; } cout<<i<<endl; } } }