3.31恒生电子笔试

/*
1.sql
利用where，orderby好像就足够ac了
---------
2.N-水仙花数
模拟过程就行
-----------

3.股票最大收益
设dp[i][k]表示前i个股票交易k次的最大值

dp[i][k]=max({dp[i][k],dp[j][k],dp[j][k-1]/history_[j]*history_[i]});//其中j<i

res=max(res,dp[i][k]);

枚举i,j,k即可
*/
#include <bits/stdc++.h>
using namespace std;
int main(){
double M;
int N,K;
cin>>M>>N>>K;
vector<double> history_;
for(int i=1;i<=N;++i){
double x;
cin>>x;
history_.push_back(x);
}
vector<double> dp[N];
double res=M;
for(int i=0;i<N;++i){
for(int k=0;k<=K;++k){
if(k==0){
dp[i].push_back(M);
continue;
}else{
dp[i].push_back(0);
}
for(int j=0;j<i;++j){
dp[i][k]=max({dp[i][k],dp[j][k],dp[j][k-1]/history_[j]*history_[i]});
}
res=max(res,dp[i][k]);
}
}
cout<<res-M<<endl;
return 0; 
}
/*
10000.0 4 2
1.0 2.0 1.0 3.0 

1000.0 1 2
1.0

1000.0 2 2
1.0 2.0
*/