AOJ 2607 : Invest Master

問題リンク : Invest Master | Aizu Online Judge

問題概要：
n日間の株価の情報が与えられる
初日にx円所持しているので、株の売買を行い最終日の所持金を最大化せよ
株の売買に手数料はかからないものとする
また、最終日の所持金の最大値は高々１０＾５である

解法：
動的計画法
最終日の所持金の最大値は高々１０＾５なので途中にその金額より大きくなることはない
また、株の売買に手数料はかからないため、その日に買った株をその日に売っても損しない
このことから、一日ごとの所持金の最大化をすればよい
dp[i] := 現在i円持っているときの翌日の所持金の最大値

コード：

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

int n,d,x,p[11][11],dp[100010];//??


int main() {
  cin >> n >> d >> x;
  rep(i,d) rep(j,n) cin >> p[i][j];
  int maxi = x;
  rep(day,d-1) {
    memset(dp,0,sizeof(dp));
    rep(i,maxi+1) dp[i] = i;
    int tmp = maxi;
    rep(i,n) {
      REP(j,p[day][i],maxi+1) {
        dp[j] = max(dp[j],dp[j-p[day][i]]+p[day+1][i]);
        tmp = max(tmp,dp[j]);
      }
    }
    maxi = tmp;
  }
  cout << maxi << endl;
  return 0;
}