Description
XiaoWei沉迷RPG无法自拔,但是他的战斗力只有5,所以他决定氪金提升战斗力。
XiaoWei购买了n个福袋。打开1个福袋后,有以下三种情况出现:
1.获得屠龙宝刀,概率为p1;
2.获得火麒麟,概率为p2;
3.什么都没获得,概率为1-p1-p2;
已知每把屠龙宝刀能够使战斗力*2,每把火麒麟能够使战斗力*1.5。XiaoWei虽然初始战斗力很弱,但是潜力无限,可以装备任意数量的屠龙宝刀和火麒麟,并且效果可以叠加。XiaoWei想知道,打开n个福袋后并装备武器后,他的战斗力期望是多少?
Input
第一行只包含一个整数T(1≤T≤100),表示有T组数据。
对于每组数据,包含1个整数n(1≤n≤20),和2个浮点数p1和p2(0≤p1,p2≤1 且 0≤p1+p2≤1)。
Output
对于每组数据,输出一行结果。
输出格式为“Case #x: y”,x表示数据组数(从1开始),y表示答案。
y以科学计数法输出,保留三位有效数字。
Sample Input
3
1 0.5 0.5
2 1 0
20 0 0
Sample Output
Case #1: 8.75e+00
Case #2: 2.00e+01
Case #3: 5.00e+00
解法:
dp[i][j][k] i表示第i个福袋,收到j个屠龙宝刀,收到k个火麒麟,以及本身的什么都没有收到
就是dp[i][j][k]=(dp[i-1][j][k]*(1-p1-p2)+dp[i-1][j-1][k]*p1+dp[i-1][j][k-1]*p2)
接下来就是把期望算一算就行
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
#include <bitset>
#include <stack>
#include <map>
#include <climits>
#include <functional> using namespace std; #define LL long long
const int INF=0x3f3f3f3f; double dp[][][],p1,p2; int main()
{
int n,t,cas=;
scanf("%d",&t);
while(t--)
{
scanf("%d%lf%lf",&n,&p1,&p2);
memset(dp,,sizeof dp);
dp[][][]=;
for(int i=; i<=n; i++)
{
for(int j=; j<=n; j++)
{
for(int k=; k<=n; k++)
{
dp[i][j][k]=dp[i-][j][k]*(-p1-p2);
if(j) dp[i][j][k]+=dp[i-][j-][k]*p1;
if(k) dp[i][j][k]+=dp[i-][j][k-]*p2;
}
}
}
double ans=;
for(int i=; i<=n; i++)
{
for(int j=; j<=n; j++)
{
double t=;
for(int k=;k<=i;k++) t=t*;
for(int k=;k<=j;k++) t=t*1.5;
ans+=t*dp[n][i][j];
}
}
printf("Case #%d: %.2e\n",++cas,ans);
}
return ;
}