[POJ 3744] Scout YYF I 题解

题意：

​ 在一条有地雷的路上，你现在的起点在 \(1\) 处。在 \(n\) 个点处布有地雷。每次有 \(p\) 的概率前进一步，\(1−p\) 的概率前进 \(2\) 步。问顺利通过这条路的概率。多组数据。

​ 数据范围：\(1 \le n \le 10\) ，\(0.25 \le p \le 0.75\) 地雷点的坐标范围：$ [1,10^8] $，答案保留七位小数。

---

题解：

\(~~~~\) 显然概率DP，设：\(dp_i\) 表示道路 \([1,i]\) 安全通过的概率 。

\(~~~~\) 则有转移方程 \(dp_i=dp_{i-1} \times p + dp_{i-2} \times (1-p)\) （\(i\) 处无雷） 。

\(~~~~\) 直接转移，时间 \(\mathcal{O(T\times 10^8)}\) ，发现时空都在 \(10^8\) 级别。

\(~~~~\) 甚至多组数据，直接狗带。

\(~~~~\) 因此要考虑优化。

优化1：矩阵快速幂

\(~~~~\) 发现转移是一维的，且最多与前两项有关。

\(~~~~\) 构造矩阵

\[\begin{bmatrix} p & 1-p \\ 1 & 0 \end{bmatrix}\quad \]

\(~~~~\) 分段对空白部分进行矩阵快速幂即可。

\(~~~~\) 时间 \(\mathcal{O(T \log 10^8)}\) ，空间完全不用考虑。

\(~~~~\) 代码：没有 不展示

优化2：数学/找规律/乱搞

\(~~~~\) 由上可知，重点在于有很多的空白部分。

\(~~~~\) 但其实空白部分在经过约 \(100\) 次DP之后数值就几乎不会变化（即变化量远远小于 \(10^7\) ）。

\(~~~~\) 以上的结论可以打表发现（ \(p=0.5\) ）：

\(~~~~\) 其实在 \(50\) 左右数值已经稳定，但考虑不可见部分可能相差过小，为稳妥我们可以将区间之间间隔 \(>100\) 的空白区域全部缩短成长度为 \(100\) 的空白区间，可以稳过。

\(~~~~\) 说白了就是可以卡精度。

\(~~~~\) 时间：\(\mathcal{O(T 100\ n)}\)

\(~~~~\) 代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int arr[25];
bool ma[5005];//存储是否是雷 
double dp[5005];
int main() {
	int n;
	double p;
	while(~scanf("%d %lf",&n,&p))
	{
		bool flag=true;
		for(int i=1;i<=n;i++) scanf("%d",&arr[i]);	
		sort(arr+1,arr+1+n);
		for(int i=0;i<n;i++)
		{
			if(arr[i+1]-arr[i]>100)
			{
				for(int j=n;j>i;j--) arr[j]-=(arr[i+1]-arr[i]-100);
			}
		}
		dp[1]=1;
		if(!flag) continue;
		for(int i=1;i<=n;i++) ma[arr[i]]=true;
		for(int i=0;i<=arr[n];i++)
		{
			if(!ma[i]) 
			{
				dp[min(i+1,arr[n]+1)]+=dp[i]*p;
				dp[min(i+2,arr[n]+1)]+=dp[i]*(1-p);
			}
			else ma[i]=false;//随时清零，省掉 memset 
			dp[i]=0;//同上 
		}
		printf("%.7f\n",dp[arr[n]+1]);
		for(int i=arr[n]-2;i<=arr[n]+2;i++) dp[i]=0;//最后需要清掉 
	}
	return 0;
}