题目大意
你有A个原料，每B个原料合成C个产品。每一次合成你可以选择下列两种buff中的任意一种：
- P%的概率合成双倍产物
- Q%的概率返还R个原料
求期望最多合成多少产品。
解法：期望dp
首先C是个系数，可以先算每B个原料合成1个产品，最后结果*C。
设 dp(i) 表示还剩下 i 个原料时的最大期望。根据题意，容易得到如下 dp 方程：
注意，B=R时需要特判,正好有B个原料时，令q=Q%，计算期望:
设：
则有：
(1) - (2)，得到：
乘上系数后与双倍产出取max即可。
时间复杂度：O(A)
出题人代码
#include<iostream>
#include<iomanip>
#include<algorithm>
using namespace std;
const int N=1e6+10;
int A,B,C,R;
double P,Q,dp[N];
int main(){
cin>>A>>B>>C>>P>>Q>>R;
P/=100;Q/=100;
for(int i=B;i<=A;i++){
dp[i]=P*(dp[i-B]+2)+(1-P)*(dp[i-B]+1);
if(B==R) dp[i]=max(dp[i],dp[i-B]+1/(1-Q));
else dp[i]=max(dp[i],Q*(dp[i-B+R]+1)+(1-Q)*(dp[i-B]+1));
}
cout<<fixed<<setprecision(15)<<C*dp[A]<<'\n';
return 0;
}