AOJ2607 Invest Master

問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2607

初めX円所持している。株式は1つも所持していない。N種類の株式がある。

  • i日目に株式jに購入すると1つの株式jを入手でき、P[i][j]だけ掛かる
  • i日目に株式jを1つ売却するとP[i][j]円入手できる

各株式について、一日に任意回数、購入と売却が可能である。
D日経過した時点で所持金を最大化せよ。
1\le N\le 10
1\le D\le 10
1\le X, P_{ij} \le 10^5


解法

購入した株式jについて、株式jをその翌日に全て売却してしまっても構わない。
翌日に売却して得となるような株式を各々の種類できるだけ購入する。個数制限なしナップザックの問題となる。

以下の様なDPを考える。

dp[今日の所持金] = 次の日の所持金

今日の所持金を元に出来るだけ株式の購入をしたら、所持金を次の日の所持金に更新する作業を入れる。

void solve() {
 
  int ans = X;
  dp[X] = X;
  rep(i, D - 1) {
    rep(j, N) {
      for(int x = 111111; x>=P[i][j]; x--) if(dp[x]) {
        dp[x - P[i][j]] = max(dp[x - P[i][j]], dp[x] - P[i][j] + P[i+1][j]);
        ans = max(ans, dp[x - P[i][j]]);
      }
    }
    rep(x, 111111) {
      dp[dp[x]] = max(dp[dp[x]], dp[x]);
    }
  }
 
  cout << ans << endl;
}