PKU : 3003, 2397 - Spiderman’s workout, Spiderman

問題概要

http://poj.org/problem?id=3003
http://poj.org/problem?id=2397

両方とも全く同じ問題です.
入力のN個の値は, 建物を上ったり下りたりするときの距離を示しています.
上るか下りるかは, こっちで勝手に決めていいですが,

• スタートは, 高さ０から
• ゴールは, 高さ０
• 途中で高さ０より下にいかないように
• 途中で上る最大の高さが一番低くなるような上り下りをする

という条件になるように.
このときの上り下りの動作を出力してください.

アルゴリズム

dp[42(何番目のステップか)][1002(現在の高さ)] = 今まで上った最大の高さ
となるように動的計画法で解けばいいです.

プログラム

どう動いたかは, long long のビット管理で行っています.
M <= 40 という条件があるからこそ動作します.

int dp[1010][1010];
ll path[1010][1010];
int t[1010];

int main(void){
  int T;
  scanf("%d",&T);

  while(T--){
    int n;
    scanf("%d",&n);
    rep(i,n){
      scanf("%d",&t[i]);
    }

    rep(i,1010) rep(j,1010) dp[i][j] = INT_MAX;
    dp[0][0] = path[0][0] = 0;

    rep(i,n){
      rep(j,1001){
        if(dp[i][j] == INT_MAX) continue;

        int pls = j + t[i];
        int mns = j - t[i];

        if(pls <= 1000 && max(j,dp[i][j]) < dp[i+1][pls]){
          dp[i+1][pls] = max(j,dp[i][j]);
          path[i+1][pls] = path[i][j];
        }

        if(0 <= mns && max(j,dp[i][j]) < dp[i+1][mns]){
          dp[i+1][mns] = max(j,dp[i][j]);
          path[i+1][mns] = path[i][j] | (1LL<<i);
        }
      }
    }

    if(dp[n][0] == INT_MAX){
      printf("IMPOSSIBLE\n");
    }
    else{
      rep(i,n){
        putchar((path[n][0] & (1LL<<(ll)i)) ? 'D' : 'U');
      }
      putchar('\n');
    }
  }
}