问题：
现在有若干个蜂巢，每个蜂巢每年有一定概率扩散 blabla，问能否预测黄蜂随时间的传播。
模型：
将华盛顿的地形离散化，变成一个二维点阵。其中，有若干个点是起始源点，每个源点每年有一定概率向周围扩散，并形成新的源点。现在，要求出每个点被覆盖的最小时间的期望。
约定：
假设资源充足，无其他人为因素干扰。
设
R
R
R 为扩散半径，
P
P
P 为每年的扩散概率。
由给定的资料显示，黄蜂的扩散范围不超过30。
设
R
=
30
,
P
=
0.6
R = 30, P = 0.6
R=30,P=0.6。
设时间阈值为
T
T
T，概率阈值为
P
′
P'
P′。
设
P
i
P_i
Pi 表示第
i
i
i 个点。
设
s
u
m
t
,
P
i
=
∑
t
′
=
0
t
P
r
o
t
′
,
P
i
sum_{t,P_i}=\sum\limits_{t'=0}^{t}Pro_{t',P_i}
sumt,Pi=t′=0∑tProt′,Pi
如果
s
u
m
T
,
P
i
sum_{T,P_i}
sumT,Pi 小于
P
′
P'
P′，可认为该点
P
i
P_i
Pi 在
T
T
T 年内无法被覆盖，期望时间为
∞
\infty
∞。
第一问的简要思路：
-
将华盛顿州的图片找出，染色，用二维点阵来表示华盛顿州，其中 m p i , j = 1 mp_{i,j}=1 mpi,j=1 表示点 ( i , j ) (i,j) (i,j) 属于华盛顿州， m p i , j = 0 mp_{i,j}=0 mpi,j=0 表示点不在华盛顿州。
-
通过动态规划来求点阵中每一个点 P i P_i Pi 恰好在第 t 年被覆盖的概率 P r o t , P i Pro_{t,P_i} Prot,Pi。
-
每个点被覆盖的最小时间的期望为 E ( P i ) = ∑ t = 0 ∞ P r o t , P i × t E(P_i) = \sum\limits_{t=0}^{\infty}Pro_{t,P_i}\times t E(Pi)=t=0∑∞Prot,Pi×t
-
根据每个点被覆盖的期望时间来画热力图。
首先考虑一个简单的模型：
有
n
+
1
n + 1
n+1 个点，其中前
n
n
n 个点已经被覆盖，现在要覆盖第
n
+
1
n+1
n+1 个点。其中，第
i
i
i 个点覆盖
n
+
1
n+1
n+1 号点的概率为
p
i
p_i
pi。那么求
n
+
1
n+1
n+1 号点被覆盖的概率
P
P
P。
设被覆盖的概率为
P
P
P，没被覆盖的概率为
P
′
P'
P′，那么：
P
=
1
−
P
′
P=1-P'
P=1−P′
根据乘法原理：
P
′
=
∏
i
=
1
n
(
1
−
p
i
)
P'=\prod\limits_{i=1}^{n}(1-p_i)
P′=i=1∏n(1−pi)
因此，
P
=
1
−
∏
i
=
1
n
(
1
−
p
i
)
P = 1-\prod\limits_{i=1}^{n}(1-p_i)
P=1−i=1∏n(1−pi)。
具体计算方面：
考虑计算
P
r
o
t
,
i
,
j
Pro_{t,i,j}
Prot,i,j。可以通过动态规划来求出。
设
F
(
P
1
,
P
2
)
F(P_1,P_2)
F(P1,P2) 表示一般情况下
P
1
(
x
1
,
y
1
)
P_1(x_1,y_1)
P1(x1,y1) 扩散到
P
2
(
x
2
,
y
2
)
P_2(x_2,y_2)
P2(x2,y2) 的概率。
因此，在第
t
t
t 年，
P
1
P_1
P1 扩散到
P
2
P_2
P2 的概率为
F
(
t
,
P
1
,
P
2
)
=
P
r
o
t
−
1
,
x
1
,
y
1
×
F
(
P
1
,
P
2
)
F(t,P_1,P_2)=Pro_{t-1,x_1,y_1}\times F(P_1,P_2)
F(t,P1,P2)=Prot−1,x1,y1×F(P1,P2)
因为
P
i
P_i
Pi 恰好第
t
t
t 年被覆盖，意味着
[
1
,
t
−
1
]
[1,t-1]
[1,t−1] 年都没被覆盖，这部分概率为
1
−
s
u
m
t
−
1
,
P
i
1-sum_{t-1,P_i}
1−sumt−1,Pi。
那么，根据上面的简单模型可得：
P
r
o
t
,
P
1
=
(
1
−
s
u
m
t
−
1
,
P
1
)
×
(
1
−
∏
(
x
,
y
)
(
1
−
F
(
t
,
P
1
,
P
2
)
)
)
Pro_{t,P_1} = (1-sum_{t-1,P_1})\times(1 - \prod\limits_{(x,y)}(1-F(t,P_1,P_2)))
Prot,P1=(1−sumt−1,P1)×(1−(x,y)∏(1−F(t,P1,P2)))
因此，我们可以得到这个算法的具体实现。
- 从 [ 1 , T ] [1,T] [1,T] 枚举 t t t
- 枚举 P 1 ( x 1 , y 1 ) P_1(x_1,y_1) P1(x1,y1)
- 枚举和 P 1 P_1 P1 距离小于 R R R 的点 P 2 P_2 P2。
- 求出 P r o t , P 1 Pro_{t,P_1} Prot,P1 和 s u m t , P 1 sum_{t,P_1} sumt,P1
- 求出每个点被覆盖的期望时间。
1 − 4 1-4 1−4 可浓缩为：从 [ 1 , T ] [1,T] [1,T] 按顺序枚举 t t t，求出 { P r o x , i , j ∣ x ∈ [ 1 , T ] , i ∈ [ 1 , w i d t h ] , j ∈ [ 1 , h e i g h t ] } \{Pro_{x,i,j}| x\in[1,T], i \in [1,width], j\in [1,height]\} {Prox,i,j∣x∈[1,T],i∈[1,width],j∈[1,height]}。