그들의 타고난 신중함에서도 소들이 홈 모기지 시장에서 돈을 많이 까먹었다.
그래서 주식시장으로 눈을 돌리려고 한다. 다행하게도 베시는 예지력이 있어 오늘의 주식 S ( 2 <= S <= 50)가격도 알지만 D(2 <= D <= 10) 날까지의 주식가격도 알수 있다
현재 가격과 앞으로의 주식 가격(1 <= PR_sd <= 1,000)이 주어지고, 투자 할 돈 M 이 주어질 때 마지막 날 최대 이윤을 얻기 위해 사고 팔 최선의 전략을 결정하라.
주식은 정수 단위로 사야하고 , 모든 돈은 다 사용할 필요는 없다. 그리고 500 000 유니트 초과한 이윤을 벌수는 없다는 것은 보장된다.
상승세인 장을 예를 들어 보자.
이 경우 두 종류의 주식이 있고 3 일의 예측치가 주어진다. 소들은 투자할 돈 10 유니트를 가진다.
오늘의가격
| 내일의가격
| | 모레의가격
주식 | | |
1 10 15 15
2 13 11 20
돈이 가용하다면 소들은 첫째날 1 번 주식을 사야 한다.
두 번째 날 첫 번째 주식을 팔고 재 빨리 2 번 주식을 사면 은행에 4 유니트가 있고 2 번 주식 한 주를 살 수 있다.
마지막 날 2 번 주식을 팔면 20 유니트의 돈을 벌수 있고 은행에 있는 4 유니트와 더하면 최종 24 유니트의 돈을 얻을 수 있다.
입력 2 3 10 10 15 15 13 11 20 출력 24
출처:usaco FEB 2009 GOLD