ZOJ 3329 【概率DP】

题意:

给你三个均匀k面筛子。

分别有k1 k2 k3个面,每个面朝上的概率是相等的。

如果第一个筛子出现a第二个筛子出现b第三个筛子出现c那么置零。

否则在当前和加上三个点数之和。

求当前和大于n需要的步数的期望。

思路:

一开始状态转移搞错了,手推公式交了WA,后来想了想状态转移的过程发现每个状态都跟0状态有关系,但是dp[0]不确定,但是幸运的是这是一个线性变换,所以状态转移的时候记录一下dp[0]的系数,最后移项输出就好了。

dp[i]=dp[i+x]*(k1*k2*k3);(x=i+j+k)(i=1...k1  j=1...k2  k=1...k3)

错误:

总的状态数量一开始脑残写成了k1+k2+k3

shit

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
double dp1[],dp2[];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,aa,bb,cc,a,b,c;
scanf("%d%d%d%d%d%d%d",&n,&aa,&bb,&cc,&a,&b,&c);
memset(dp1,,sizeof(dp1));
memset(dp2,,sizeof(dp2));
for(int w=n; w>=; w--)
{
for(int i=; i<=aa; i++)
{
for(int j=; j<=bb; j++)
{
for(int k=; k<=cc; k++)
{
if(i==a&&j==b&&k==c)
{
dp2[w]+=1.0/(aa*bb*cc);
}
else
{
dp2[w]+=dp2[w+i+j+k]/(aa*bb*cc);
dp1[w]+=dp1[w+i+j+k]/(aa*bb*cc);
}
}
}
}
dp1[w]+=;
}
printf("%.15lf\n",dp1[]/(-dp2[]));
}
}
上一篇:常用sql语句及案例(oracle)


下一篇:Java-HttpServletRequest