D.四倍大甜甜花题解

admin 2024-12-16 13:00:02 2024-12-16 13:03:37

题目大意

你有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;
}