yukicoder : No.664 超能力者Aと株価予測

なんか既視感のある問題だったけど違うのかな。
https://yukicoder.me/problems/no/664

問題

今後(N+1)分の間の株価の遷移A[i]がわかっているものとする。
初期状態で資金がKあり、株の売買をMセット行える場合、最適な株の売買を行うと、資金を最大どの程度に増やすことができるか。

解法

株は全力で買って全力で売る、を繰り返すのが良く、細々買ったり売ったりする利点はない。
f(N,M) := N分目までにおいて計M回株を倍々した状態の最大資金
とする。

N日目に株を売買しない場合と、N日目に株を売る場合を考えよう。
後者については、その時売る株をいつ買うのかを総当たりしよう。
すなわち をDPで求めればよい。

int N,M,K;
int A[400];

ll dp[404][21];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	FOR(i,N+1) cin>>A[i];
	
	ll ret=K;
	dp[0][M]=K;
	for(i=1;i<=N;i++) {
		for(j=0;j<=M;j++) {
			dp[i][j]=max(dp[i][j],dp[i-1][j]);
			if(j<M) for(x=0;x<i;x++) dp[i][j]=max(dp[i][j],dp[x][j+1]%A[x]+dp[x][j+1]/A[x]*A[i]);
			ret=max(ret,dp[i][j]);
		}
	}
	
	cout<<ret<<endl;
	
	
}

まとめ

チーター本でも株価増減を見て資金を増やす問題があったね。