AOJ 2607 : Invest Master
問題リンク : Invest Master | Aizu Online Judge
問題概要:
n日間の株価の情報が与えられる
初日にx円所持しているので、株の売買を行い最終日の所持金を最大化せよ
株の売買に手数料はかからないものとする
また、最終日の所持金の最大値は高々10^5である
解法:
動的計画法
最終日の所持金の最大値は高々10^5なので途中にその金額より大きくなることはない
また、株の売買に手数料はかからないため、その日に買った株をその日に売っても損しない
このことから、一日ごとの所持金の最大化をすればよい
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; }