rnqoj-103-最大老本-dp
rnqoj-103-最大利润-dp
参见:http://www.bgy.gd.cn/diannao/20011/6nj/olimpic/%B5%E7%C4%D4%D7%A8%CC%E2%D1%B5%C1%B7%A3%A84%A3%A9.htm
神题啊~~~
dp[i][j]: 第i次试验,剩余j的药品,从第i次试验到第m次试验的最大利润。
c[i]: 第i次试验到第m次试验,j克药品的平均价值。
c[m]=max(a,b);
if((a-b)+c[i+1]*(p-q)<=0)
c[i]=1.0*b+1.0*c[i+1]*q;
else
c[i]=1.0*a+1.0*c[i+1]*p;
#include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> using namespace std; double c[51]; double a,b; double p,q; int main() { int m,n,i; while(~scanf("%d%d%lf%lf%lf%lf",&m,&n,&a,&b,&p,&q)) { c[m]=max(a,b); p=1-p; q=1-q; for(i=m-1;i>=1;i--) { if((a-b)+c[i+1]*(p-q)<=0)c[i]=1.0*b+1.0*c[i+1]*q; else c[i]=1.0*a+1.0*c[i+1]*p; } printf("%.5lf\n",c[1]*n); } }