推一下蒟蒻 $\color{limegreen}{\texttt {博客}}$ ～

原题链接~

看到楼上下的大佬都开的是二维数组，实则不需，蒟蒻在这里给出一种反复利用一个一维数组的解法 $QwQ$ 。

$\color{salmon}{\texttt {先设置状态～}}$

按着期望 $DP$ 的套路走，设置 $dp_{\ i}$ 表示：取到 $i$ 件不同的物品，所期望取的天数。

这一设置状态的思路甚至可以延用到 [SHOI2002]百事世界杯之旅 和 收集邮票 两道蓝题里。（说实话，我觉得这道黄题比那两道蓝题不知道高到哪里去了。）

$\color{violet}{\texttt {再考虑转移～}}$

我们提到：$dp_{\ i}$ 代表的状态是 取到了 $i$ 件不同的物品 。

考虑什么情况下会造就这种状态。无非两种：

  • 原来有 $i-1$ 个物品，一发出货，从 $dp_{\ i-1}$ 转移过来，这样的概率是 $\dfrac{K-(i-1)}{K}=\dfrac{K-i+1}{K}$

_注：即卡池（误）里有 $K$ 个物品，自己已经有了 $i-1$ 个，那还有 $K-i+1$ 个是自己没有的，抽这些即能使自己多获得一种物品_

  • 早就有 $i$ 个物品了，抽一发沉了 （是我没错了） ，从 $dp[i]$ 转移过来，这样的概率是 $\dfrac{i}{K}$

_注：含义同上_

那么我们就可以列出一个方程辣：

为了防止爆精写成这样更为稳妥：

随着时间的推移， 每一天 都会面临一次这样的转移，因为每一天的抽卡都存在有出货与不出货的概率。（赌狗一无所有）

$\color{blueviolet}{\texttt {最后计划转移方式～}}$

这个式子对于每一天的状态 独立成立 ，说人话就是：

当天 的 $dp_{i-1}$ 不能影响 当天 $dp_i$ 的转移，用来转移 $dp_i$ 的 $dp_{i-1}$ 是 上一天 的 $dp_{i-1}$ 。

存在一种感性理解就是：我今天抽卡的卡池，实则用的是我 昨天 抽完以后的卡池。

那么，为了防止 $dp_{i-1}$ 的更新影响 $dp_{i}$ 的更新，我们选择 倒序跑 $for$ 。

记录第 $d$ 天抽满 $K$ 个物品的概率，即当时的 $dp_{\ K}$ 。存这个值于 $ans_{\ d}$

最后对于每一个询问，扫一遍 $ans$ ，找到最小的 $d$ 满足条件，输出即可。

$\color{royalblue}{\texttt {代码如下：}}$

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
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
const long double EPS = 1e-8;
const int MAX = 1e3 + 7;
long double dp[MAX];
long double ans[MAX << 3];
//楼上大佬已经证过，最大的期望天数跑不出 1000*ln(1000) 
//这里用*8 代替 *ln(1000)
int main()
{
	int K, M;
	cin >> K >> M;
	dp[0] = 1.0;
	for (int i = 1; i <= 8000; i++)
	{
		for (int j = K; j > 0; j--)//倒序扫
		{
			dp[j] = (dp[j - 1] * (K - j + 1) + dp[j] * j) / (K * 1.0);
            //转移
		}
		ans[i] = dp[K];//记录 dp[k]
		dp[0] = 0;
	}
	while (M--)
	{
		int p;
		cin >> p;
		for (int i = 1; i <= 8000; i++)
		{
			if (ans[i] * 2000 >= p - EPS)//防炸精写法
			{
				cout << i << "\n";
				break;
			}
		}
	}
}

最后更新： 2021年04月19日 11:44

原始链接： https://quest233.github.io/2021/04/17/%E6%B5%85%E8%B0%88%E4%B8%80%E7%B1%BB%E7%AE%80%E5%8D%95%E6%9C%9F%E6%9C%9BDP%E2%80%94%E2%80%94-CF768D-Jon-and-Orbs%E9%A2%98%E8%A7%A3/