[ZSOI 股票投资]包含贪心思想的动态规划

Description

Input

Output

对每组数据，输出一行，包含一个保留3位小数的实数，表示你能获得的最多现金。答案保证不会超过1e15。

Sample Input

1
5000 0.001 5 0.003
6
20 21 20 19 20 19

Sample Output

5332.000

【算法分析】
容易发现，如果是最优解的话，必然可以将时间划分成x个阶段，
每个阶段是由一个尽量买，和一个尽量卖所组成。
然后,
F[i]表示第i天最多剩多少现金

Gmax[i]表示第i天最多持有多少股
Grest[i]表示第i天持Gmax[i]股，剩下最多多少钱。
然后转移时就分当前位置是尽量买之后的和尽量卖之后的讨论。
维护一下就可以了。
【CODE】
#include #include #include const int N=30005;
const int INF=1000000000;
int n,tot;
double C,S1,S2,T,prize[N],F[N],Gmax[N],Grest[N];

inline double max(double x,double y){return x>y?x:y;}

double Buy(double x,double p){
int l=0,r=INF,mid;
double G;
while (l+1 mid=(l+r)/2;
G=p*mid*100;
if (G+G*T+max(G*S1,S2)<=x) l=mid;
else r=mid-1;
}
G=p*r*100;
if (G+G*T+max(G*S1,S2)<=x) return 100.0*r;
else return 100.0*l;
}

double Rest(double x,double b,double p){
double G=b*p;
return x-(G+G*T+max(G*S1,S2));
}

double Sell(double b,double r,double p){
double G=b*p;
return r+G-G*T-max(G*S1,S2);
}

void dp(){
int i;
double k;
memset(F,0,sizeof(F));
F[0]=C; Gmax[0]=0; Grest[0]=C;
for (i=1;i<=n;i++){
Gmax[i]=Gmax[i-1];
Grest[i]=Grest[i-1];
F[i]=max(F[i-1],Sell(Gmax[i],Grest[i],prize[i]));
k=Buy(F[i-1],prize[i]);
if (Gmax[i] Grest[i]=Rest(F[i],k,prize[i]);
Gmax[i]=k;
}
}
printf("%.3lfn",F[n]);
}

int main(){
freopen("stock.in","r",stdin);
freopen("stock.out","w",stdout);
int Tc;
scanf("%d",&Tc);
for (int i=1;i<=Tc;i++){
scanf("%lf%lf%lf%lf%d",&C,&S1,&S2,&T,&n);
for (int i=1;i<=n;i++) scanf("%lf",&prize[i]);
dp();
}
}