Problem 0234 : Aizu Buried Treasure
解法
掘った道を戻るときはコストがかからず、酸素の補給もされない。
したがって今まで掘った道を覚えておく必要がある。
どう覚えるかであるが、すでに掘った道は左右には動けるが、上には戻れないので、その深さにおける"掘った区間"だけを覚えておけばよいことがわかる。
dp[i][j][k][l][r]を深さiまで掘って、現在左からj列目にいて、酸素の残りがkで、
区間l≦x≦rを掘ってあるときの最小費用とする。
テーブルの更新順序は以下のようにする。
深さi→区間の幅range→酸素の量→区間の左端→現在位置
ただし現在位置は区間左端から右端までと、右端から左端までと1往復する必要がある。
(区間の端にいて、区間の途中まで戻って掘る場合があるため)
また、酸素の量の条件が微妙にわかりにくいので注意する。(ここでずっとはまってた)
- 酸素は、最下段では1になった状態で終了してよい。0はだめ。
- その他の段では、動いた後で1になると、次に動いたときに酸素が0になるので、ゲームオーバーになる
ソースコード
すんごい見にくい。
int w,h,f,m,o; int c[10][10],dp[11][10][51][10][10]; int main(){ while(cin>>w>>h,w){ cin>>f>>m>>o; rep(i,h)rep(j,w)cin>>c[i][j]; rep(i,h+1)rep(j,w)rep(k,m+1)rep(l,w)rep(r,w)dp[i][j][k][l][r]=inf; rep(i,w)dp[0][i][o][i][i]=0; rep(i,h)rep(range,w)for(int k=m;k>1;k--) rep(it,2)rep(l,w-range)rep(x,range+1){ int r=l+range,j=it?l+x:r-x,cost=dp[i][j][k][l][r]; if(cost==inf)continue; if(c[i][j]>0){ int sanso=min(m,k-1+c[i][j]); dp[i+1][j][sanso][j][j]=min(dp[i+1][j][sanso][j][j],cost); } else{ dp[i+1][j][k-1][j][j]=min(dp[i+1][j][k-1][j][j],cost-c[i][j]); } if(i==0)continue; if(j>0){ if(l<j)dp[i][j-1][k-1][l][r]=min(dp[i][j-1][k-1][l][r],cost); else{ if(c[i-1][j-1]>0){ int sanso=min(m,k-1+c[i-1][j-1]); dp[i][j-1][sanso][l-1][r]=min(dp[i][j-1][sanso][l-1][r],cost); } else{ dp[i][j-1][k-1][l-1][r]= min(dp[i][j-1][k-1][l-1][r],cost-c[i-1][j-1]); } } } if(j<w-1){ if(j<r)dp[i][j+1][k-1][l][r]=min(dp[i][j+1][k-1][l][r],cost); else{ if(c[i-1][j+1]>0){ int sanso=min(m,k-1+c[i-1][j+1]); dp[i][j+1][sanso][l][r+1]=min(dp[i][j+1][sanso][l][r+1],cost); } else{ dp[i][j+1][k-1][l][r+1]= min(dp[i][j+1][k-1][l][r+1],cost-c[i-1][j+1]); } } } } int ans=inf; rep(i,w)for(int j=1;j<=m;j++)rep(l,w)rep(r,w)ans=min(ans,dp[h][i][j][l][r]); if(ans>f)cout<<"NA"<<endl; else cout<<ans<<endl; } return 0; }