![見出し画像](https://assets.st-note.com/production/uploads/images/31604152/rectangle_large_type_2_2b8c9db99d37163f29b983089188b95b.jpg?width=1200)
M-SOLUTIONS プロコンオープン 2020見直し D - Road to Millionaire
問題
n日間のある株の株価が与えられるので、売買を行い手持ちの資金1000円が最大になる場合の金額を返す問題。ちなみに売買に手数料はかからないと言う夢の様な世界。
作成した解答(Python:33ms)
n = int(input())
a = [int(i) for i in input().split()]
assets = 1000
for i in range(n - 1):
if a[i] < a[i + 1]:
assets = assets//a[i] * a[i + 1] + assets%a[i]
print(assets)
解説
資金を最大化するためには、安いときに買って高いときに売れば良い。例えば以下の数列が与えられたとすると
100, 130, 130, 150, 115, 115, 150
以下の様に2日を比較して、金額が上がっている場合には売買すれば良い
解説動画を見て作成した解答(CPP:8ms)
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using vi = vector<int>;
int main() {
int n;
cin >> n;
vi a(n+1);
rep(i, n) cin >> a.at(i+1);
vector<ll> dp(n+1);
dp.at(0) = 1000;
for (int k = 1; k <= n; k++) {
dp.at(k) = 0;
for (int i = 0; i < k-1; i++) {
int m = 99999;
for (int j = i+1; j < k; j++){
m = min(m, a.at(j));
}
dp.at(k) = max(dp.at(k), dp.at(i)/m*a.at(k)+dp.at(i)%m);
}
}
ll x = 0;
rep(i, n+1) x = max(x, dp.at(i));
cout << x << endl;
return 0;
}
DP(Dynamic Programming)を利用して解答しているらしいけど、良くわからなかったから、以下の投稿を参照しようと思った。
この記事が気に入ったらサポートをしてみませんか?