题目大意

你有A个原料，每B个原料合成C个产品。每一次合成你可以选择下列两种buff中的任意一种：

• P%的概率合成双倍产物
• Q%的概率返还R个原料

求期望最多合成多少产品。

解法：期望dp

首先C是个系数，可以先算每B个原料合成1个产品，最后结果*C。
设 dp(i) 表示还剩下 i 个原料时的最大期望。根据题意，容易得到如下 dp 方程：

$$dp(i) = max\{ P\%×(dp(i−B)+2)+(1−P\%)×(dp(i−B)+1),Q\%×(dp(i−B+R)+1)+(1−Q\%)×(dp(i−B)+1)\}$$

注意，B=R时需要特判,正好有B个原料时，令q=Q%，计算期望:

$$E=(1-q)*1+(1-q)*q*2+(1-q)*q^2*3+\cdots=(1-q)\sum_{i=0}^{\infty}q^i(i+1)$$

设：

$$S=\sum_{i=0}^{\infty}q^i(i+1) \tag{1}$$

则有：

$$qS=\sum_{i=1}^{\infty}q^ii \tag{2}$$

(1) - (2)，得到：

$$E=(1-q)S=\sum_{i=0}^{\infty}q^i=\frac{1}{1-q}$$

乘上系数后与双倍产出取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;
}