PKU 2465 Adventures in Moving - Part IV
http://poj.org/problem?id=2465
200lの燃料タンクを持つトラックである距離を走行する。
このトラックは丁度1lで1km走ることができる。
途中にはいくつかのガソリンスタンドがあり、スタート地点から距離と燃料1lの値段がわかっている。
この時、トラックは目的地についた時に燃料が半分以上残っているようにしたい。
最も安く目的地に着くときの値段を求めろというような問題。
燃料が半分より多く残っているのが最適解となる場合や、もしかしたら、一旦目的により遠くに行って、そこで燃料を補給して戻ってくるパターンまで考えないといけないかもしれません。
結構ぬけててたくさんWAをもらいました。
PI in[200]; ll dp[200][300]; main(){ int ki; cin>>ki; int sz=0; while(cin>>in[sz].F>>in[sz].S)++sz; rep(i,200)rep(j,300)dp[i][j]=1LL<<50LL; sort(in,in+sz); if(100-in[0].F>=0){ dp[0][100-in[0].F]=0; for(int i=100-in[0].F+1;i<=200;++i)dp[0][i]=min(dp[0][i],dp[0][i-1]+in[0].S); } for(int i=1;i<sz;++i){ if(in[i].F-in[i-1].F<=200)dp[i][0]=min(dp[i][0],dp[i-1][in[i].F-in[i-1].F]); for(int j=1;j<=200;++j){ if(in[i].F-in[i-1].F+j<=200)dp[i][j]=min(dp[i][j],min(dp[i][j-1]+in[i].S,dp[i-1][in[i].F-in[i-1].F+j])); else dp[i][j]=min(dp[i][j],dp[i][j-1]+in[i].S); } } ll ans=1LL<<50LL; for(int i=0;i<sz;++i){ int dist=abs(in[i].F-ki); for(int j=100+dist;j<=200;++j)ans=min(ans,dp[i][j]); } if(ans>=(1LL<<50LL))cout<<"Impossible"<<endl; else cout<<ans<<endl; }