URAL-1716 Alternative Solution 题解

这是一道代码量奇小但思维量贼大的 dp。

题意

有一个骗分程序，它要试图通过一个有 $n$ 个测试点的测试，每个测试点的答案是 YES 或者 NO。有一条线索，答案文件有 $s$ 个字节，并且已知 YES 占用 $3$ 个字节，No 占 $2$ 个字节。程序的实现如下功能：如果前面没有测试点，就输出 YES；如果前面有测试点，就输出上一个测试点的答案。
现在给出 $n$ 和 $s$，请计算错误的测试点数的期望值。答案误差不超过 $10^{-5}$ 都算对。（$1\le n\le 5000,2n\le s\le 3n$）

样例

输入：

3 7

输出：

2.000000

说明：
有 $2$ 个 NO，$1$ 个 YES，有三种排列方法：

1. YES NO NO：错了第 $2$ 个测试点，错 $1$。
2. NO YES NO：全错了，错 $3$。
3. NO NO YES：错了第 $1$、$3$ 个测试点，错 $2$。

平均一下就是错了 $2$ 个。

思路

可以发现，如果默认第 $0$ 个测试点是 YES，那么最终的错误数就是有几个相邻的测试点的答案不同。而且根据 $n$ 和 $s$ 可以使用鸡兔同笼的基本思想算出 YES 的数量 $cnty$ 和 NO 的数量 $cntn$。
期望值 dp。设 $d{p}_{i,j,k}$ 表示从第 $n$ 个测试点到第 $i$ 个测试点，第 $i+1$ 个到第 $n$ 个测试点用完后还剩 $j$ 个 NO，第 $i$ 个测试点是 k=0:YES k=1:NO，错误测试点数的期望值。
在看接下来的转移式和答案时，可以思考：

1. 为什么要倒着 dp？
2. 为什么 $j$ 表示的是第 $i+1$ 到 $n$ 个而不是从第 $i$ 个开始？

先抛出式子，等会解释：

if(i-j!=cnty) f[i][j][k]+=(f[i+1][j][0]+(k!=0))*(cnty-(i-j))/(n-i);
if(j!=cntn) f[i][j][k]+=(f[i+1][j+1][1]+(k!=1))*(cntn-j)/(n-i);

如果 $1$ 到 $i$ 中还有 $j$ 个 NO 要用，那 $1$ 到 $i$ 中就还有 $i-j$ 个 YES 要用。由此可得在 $i+1$ 到 $n$ 中用了 $cntn-j$ 个 NO 和 $cnty-(i-j)$ 个 YES。f[i+1][j][0]+(k!=0) 和 f[i+1][j+1][1]+(k!=1) 还是好理解的，如果第 $i+1$ 个的 YES/NO 和第 $i$ 个不同就会多错一个测试点，第 $i+1$ 个如果用的是 NO（1）剩余的 NO 数量就会从 $j+1$ 变成 $j$。后面的那坨是啥？
(cnty-(i-j))/(n-i) 代表着第 $i+1$ 个用的是 YES 的概率，(cntn-j)/(n-i) 代表着第 $i+1$ 个用的是 NO 的概率，也就是 f[i+1][j][0] 和 f[i+1][j+1][1] 是 f[i][j][k] 的上一步的概率。
倒着看似乎很难理解，那我们先正过来。假设现在到了第 $i$ 个测试点，还剩 $x$ 个 YES 没有用，$y$ 个 NO 没有用，那么第 $i+1$ 个是 YES 的概率是？$\frac{x}{x+y}$。说白了就是在 $x+y$ 个球里面随机抓一个，抓出来是 YES 的概率是多少。NO 的概率就是 $\frac{y}{x+y}$。再把它倒过来，cnty-(i-j) 就是正着的时候用到第 $i$ 个测试点，还剩下几个 YES，而 n-i 就是剩下给 $i+1$ 到 $n$ 用的 YES/NO 总数。
前面的特判，i-j!=cnty 表示在 $i+1$ 到 $n$ 中有 YES，所以剩余给 $1$ 到 $n$ 的 YES 不是全部的 YES，j!=cntn 同理。
答案就是 $d{p}_{0,0,0}$，意思是到了第 $0$ 个测试点，这个测试点是 YES，第 $1$ 到 $n$ 个测试点用完后还剩 $0$ 个 NO（即全部用完）的错误数期望值。此时倒着做就体现出了优势，因为最终答案是确定的一个状态，第 $0$ 个测试点是 YES 解决了程序的特殊情况：前面没有测试点。$j$ 表示 $i+1$ 到 $n$ 的剩余数不仅使计算概率更加方便，而且不需要在 $cnty$ 上额外加上第 $0$ 个测试点的 YES。

代码

会 MLE，所以应当滚动数组，注意每次在累加 $d{p}_{i,j,k}$ 前应当清零。

#include<bits/stdc++.h>
using namespace std;
int n,s,cnty,cntn;
long double f[2][5005][2];
int main(){cin>>n>>s;cnty=s-2*n;cntn=n-cnty;bool fl=0;for(int i=n-1;i>=0;i--,fl^=1)for(int j=0;j<=cntn;j++)for(int k=0;k<2;k++){f[fl][j][k]=0;if(i-j!=cnty) f[fl][j][k]+=(f[fl^1][j][0]+(k!=0))*(cnty-(i-j))/(n-i);if(j!=cntn) f[fl][j][k]+=(f[fl^1][j+1][1]+(k!=1))*(cntn-j)/(n-i);}cout<<fixed<<setprecision(10)<<f[fl^1][0][0]<<endl;return 0;
}