# 题解 SP1026 【FAVDICE - Favorite Dice】

技术文章 1年前 (2020) 完美者
566 0

标签:不同的   代码   ace   scanf   can   滚动数组   并且   注意   pre   

首先,这是一道经典的期望dp题

因为最终状态 $ (所有面都被筛到过) $ 是确定的,所以才用 逆推 ,设状态

$ f[i] $ 表示已经筛到了 $ i $ 个不同的面,有 $ i\over n $ 的概率是由$ f[i] $ 转移而来的,

也就是筛到了之前筛过的面,有 $ {n-i\over n} $ 的概率是由 $ f[i+1] $
转移得到的,

也就是呢,筛到了一个之前没有筛到过的面,并且无论从哪里来,这次的期望次数都

比原来的期望次数多 $ 1 $,所以就得到了转移方程:

$ f[i] = {i \over n} \times f[i] + {n-i \over n} \times f[i+1] $;

注意把 $ f[i] $ 化简到一边;

另外,可以用滚动数组的;

$ f[i]=f[i+1]+n/(n-i) $;

AC 代码

#include<iostream>
#include<cstdio>
using namespace std;
int n,T;
double g[2];
int main(){
	int i;
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		g[n&1]=0;
		i=n-1;
		for(;i>=0;i--) g[i&1]=1.0*g[(i+1)&1]+1.0*n/(n-i);
		printf("%0.2f\n",g[0]); 
	}
}

# 题解 SP1026 【FAVDICE - Favorite Dice】

标签:不同的   代码   ace   scanf   can   滚动数组   并且   注意   pre   

原文地址:https://www.cnblogs.com/Aswert/p/13635057.html

版权声明:完美者 发表于 2020-09-17 19:00:17。
转载请注明:# 题解 SP1026 【FAVDICE - Favorite Dice】 | 完美导航

暂无评论

暂无评论...