codeforces-768-d-Jon and Orbs-概率dp

题目链接

感觉最近几场cf的后面几题都是树，而且大同小异……博客里面树太多了……放道dp压压惊……这场cf很是惨淡啊……c题跟b题一样注意到了数据范围的奇特性，但是还是强行猜测有循环节……果不其然的gg了……b题被特判坑数据fst了……还是太菜了……其实当时应该开这个D题的，这个题目并不难，自己推推也就一会的事……不该跟风去看什么E博弈论的……

题意：不知名的男主有个东西，那个东西每天会下一个球。男主为了抵御白学家（原文是white walkers……第一眼真的看成了white leaners……大限将至了……）需要有k（k<=1e3）种不同颜色的球每个至少一个。已知男主的那个东西每天下的球是k种颜色之一，且每种颜色等可能。现有q(q<=1e3)次询问，每次询问一个数pi，问多少天以后男主能抵御白学家的概率大于等于(pi-1e-7)/2000

思路：一开始没太能看懂题意……自己举几个例子之后就能明白了，这个概率题还算比较良心，可以举例子观察一下……按照天数与球的种数来划分状态，设dp[i][j]表示I天时有j种球的概率，那么很容易得到递推式：dp[i][j]=dp[i-1][j]j/k+dp[i-1][j-1](k-(j-1))/k.
其中前一项表示在i-1天时已有j种球，第二项表示i-1天有(j-1)种球。因为询问比较多，对于每个k预处理dp数组就行了。不过要注意天数的枚举范围，一开始天数的枚举范围小了然后wa了一发……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<stdio.h>
#include<math.h>
using namespace std;
double dp[10003][1003];
double ans[10003];
int main()
{
	long long k,p,n,q;
	scanf("%I64d%I64d",&k,&q);
    dp[1][1]=1;
	for(int i=2;i<=10000;i++)
	 for(int j=1;j<=k;j++)
	 {
	 	dp[i][j]=dp[i-1][j]*j/k+dp[i-1][j-1]*(k-j+1)/k;
	 }
	for(int i=1;i<=10000;i++) 
     {
       ans[i]=dp[i][k]; 
	  }
	 for(int i=1;i<=q;i++)
	 {
	 	int x;
	 	scanf("%d",&x);
	    for(int j=1;j<=10000;j++)if(ans[j]>(double)x/2000)
	    {
	    	printf("%d\n",j);
	    	break;
		}
	 }  
	 return 0;
}