Problem 0234 : Aizu Buried Treasure

問題概要

日本語なので本文参照。
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0234&lang=jp

解法

掘った道を戻るときはコストがかからず、酸素の補給もされない。
したがって今まで掘った道を覚えておく必要がある。
どう覚えるかであるが、すでに掘った道は左右には動けるが、上には戻れないので、その深さにおける"掘った区間"だけを覚えておけばよいことがわかる。


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;
}