3413 - RPG

POJ

http://poj.org/problem?id=3413

問題

N個のクエストをクリアすることを考える。
クエストは任意の順番に挑戦することが出来る。
挑戦するときの経験値によってクエストをクリアできる確率が変わる。
N個のクエストをクリアする確率の最大値とその順番を求めよ。

解法

bitDP。
dp[クエストの部分集合]=そのクエストを全てクリアする確率の最大値
経験値は現在のクエストの部分集合を見て計算すればいい。

ソース

int main() {
  int n,d;
  cin >> n >> d;
  int a[n],b[n],s[n];
  REP(i,n) {
    cin >> a[i] >> b[i] >> s[i];
  }
  double dp[1<<n];
  REP(i,1<<n) dp[i] = 0;
  dp[0] = 1;
  int prev[1<<n];
  REP(S,1<<n) {
    int xp = d;
    REP(i,n) {
      if (S>>i&1)
        xp += s[i];
    }
    REP(i,n) {
      if (!(S>>i&1)) {
        if (xp < a[i]) {
          if (dp[S|(1<<i)] == 0) {
            prev[S|(1<<i)] = S;
          }
        } else if (xp >= a[i] && xp < b[i]) {
          if (dp[S|(1<<i)] < dp[S] * (xp-a[i])/(b[i]-a[i])) {
            dp[S|(1<<i)] = dp[S] * (xp-a[i])/(b[i]-a[i]);
            prev[S|(1<<i)] = S;
          }
        }else if (xp >= b[i]) {
          if (dp[S|(1<<i)] < dp[S]) {
            dp[S|(1<<i)] = dp[S];
            prev[S|(1<<i)] = S;
          }
        }
      }
    }
  }
  printf("%.5f\n",dp[(1<<n)-1]);
  int S = (1<<n)-1;
  vector<int> res;
  while(S) {
    int hoge = S^prev[S];
    REP(i,n) {
      if (hoge>>i & 1) {
        res.push_back(i+1);
        break;
      }
    }
    S = prev[S];
  }
  reverse(ALL(res));
  REP(i,res.size()) {
    if(i)cout << " ";
    cout << res[i];
  }cout << endl;
}