概率DP light oj 1030

t组数据

n块黄金

到这里就捡起来 出发点1 到n结束  点+位置>n 重掷一次

dp[i] 代表到这里的概率

dp[i]=(dp[i-1]+dp[i-2]... )/6  如果满6个的话

否则处理一下

然后期望就是 sum+=dp[i]*z[i];

 #include <stdio.h>
#include<algorithm>
#include<math.h>
#include<string.h> using namespace std; #define MAXN 100010 double dp[MAXN];
int z[MAXN]; int main()
{
int t,ca;
scanf("%d",&t);
ca=; while (t--)
{
int n;
scanf("%d",&n); for(int i=;i<=n;i++)
scanf("%d",&z[i]);
memset(dp,,sizeof(dp)); dp[]=; for(int i=;i<n;i++)
{
int x=min(n-i,); for(int j=;j<=x;j++)
dp[i+j]+=dp[i]/x;
}
double sum=;
for(int i=;i<=n;i++)
{
sum=sum+dp[i]*z[i];
}
printf("Case %d: %.6lf\n",ca++,sum);
} return ;
}
上一篇:android之ViewPager


下一篇:[Guava源码分析] Preconditions 前置条件