“纵使天地渺远，空间永远不够。”
“即便今昔深邃，时间不可窥探。”
概率期望 dp
期望 x 概率 x 动态规划
概率的定义：
对于事件 $A$ ，在进行了多次试验时候，其发生的次数与总实验次数之比 $\frac{N_A}{n}$ 会逐渐稳定在某一数值 $p$ 的附近，则 $p$ 被称为 $A$ 在该条件下发生的概率，记为 $P(A)=p$ 。
期望的定义：
对于一个事件 $A$ ，如果 $A$ 的结果有 $k$ 种，每一种结果的权值为 $a_i$ ，概率为 $p_i$ ，则 $A$ 事件的期望记为 $E(A)$ ，则有 $E(A)=\sum\limits_{i=1}^{k} a_ip_i$ 。
概率 dp
采用顺推法，从初始状态（一般来说是 $dp_{0,0..0}$ ）到所有的限制，同一般的 DP 类似的，难点依然是对状态转移方程的刻画，只是这类题目经过了概率论知识的包装。
例题 CF148D Bag of Mice
参考资料
AC Code
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| #include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
typedef long long ll;
using namespace std;
const int MAXN=1e3+1;
template<class T>
inline void read(T &x)
{
x=0;
char ch=gh(),t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
return x>y?x=y,1:0;
}
int W,B;
double dp[MAXN][MAXN];
int main()
{
read(W,B);
for(int i=1;i<=W;++i) dp[i][0]=1.0;
for(int i=1;i<=B;++i) dp[0][i]=0;
for(int i=1;i<=W;++i)
for(int j=1;j<=B;++j)
{
double ix=i,jx=j;
dp[i][j]+=(double)(ix/(ix+jx));
if(j>=3) dp[i][j]+=double(jx/(ix+jx))*double((jx-1)/(ix+jx-1))
*double((jx-2)/(ix+jx-2))*dp[i][j-3];
if(i>=1&&j>=2) dp[i][j]+=double(jx/(ix+jx))*dp[i-1][j-2]
*double((jx-1)/(ix+jx-1))*double(ix/(ix+jx-2));
}
printf("%.9lf",dp[W][B]);
return 0;
}
|
期望 dp
正难则反，这是亘古不变的真理。
设有事件 $A$ ，则有 $dp[x]$ 表示在 $x$ 次实现之后 $A$ 满足某种条件 $T$ 的期望。一般而言，如果有 $dp[M]=1$ ，则采用逆序推理，否则有 $dp[0]=0$ ，然后顺序推理。
接下来 $4$ 道题，都是对期望 $\text{dp}$ 的讲解。
例题
用 $dp[x]$ 表示当前已经投掷了 $x$ 面，投到 $n$ 面的期望次数。
对于 $dp[n]$ ，因为我们已经投掷了 $n$ 面了，所以不需要再投就可以满足条件，所以有 $dp[n]=0$ 。
AC Code
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
typedef long long ll;
using namespace std;
template<class T>
inline void read(T &x)
{
x=0;
char ch=gh(),t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
return x>y?x=y,1:0;
}
int T,N;
double dp[1001];
int main()
{
read(T);
while(T--)
{
read(N);
dp[N]=0;
for(int i=N-1;i>=0;--i)
dp[i]=dp[i+1]+1.0*N/(N-i);
printf("%.2lf\n",dp[0]);
}
return 0;
}
|
能够被称为是期望 dp 的模板题，虽然我没有这么觉得。
因为 $v\le 300$ ，则保证了我们求出全源最短路的复杂度，使用 Floyd 的 $\mathcal O(n^3)$ 求出并在 $\mathcal O(1)$ 内查询。
然后其实就会变成一个标准的概率期望的动态规划问题：
这应该是我写过最复杂的式子了。
AC Code
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
| #include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
typedef long long ll;
using namespace std;
const int MAXN=2e3+1;
const int MAXM=2e3+1;
const int MAXV=3e2+1;
template<class T>
inline void read(T &x)
{
x=0;
char ch=gh(),t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
return x>y?x=y,1:0;
}
int N,M,V,E;
int Now[MAXN],Oth[MAXN];
double p[MAXN],dp[MAXN][MAXM][3];
int Dist[MAXV][MAXV];
inline void Floyd()
{
for(int k=1;k<=V;++k)
for(int i=1;i<=V;++i)
for(int j=1;j<=V;++j)
Dist[i][j]=min(Dist[i][j],Dist[i][k]+Dist[k][j]);
}
int main()
{
memset(Dist,0x3f,sizeof(Dist));
read(N,M,V,E);
for(re int i=1;i<=N;++i) read(Now[i]);
for(re int i=1;i<=N;++i) read(Oth[i]);
for(re int i=1;i<=N;++i) scanf("%lf",&p[i]);
for(int i=1,u,v,w;i<=E;++i)
{
read(u,v,w);
Dist[u][v]=Dist[v][u]=min(Dist[u][v],w);
}
Floyd();
for(int i=1;i<=V;++i) Dist[i][i]=Dist[i][0]=Dist[0][i]=0;
for(int i=1;i<=N;++i)
for(int j=0;j<=M;++j)
for(int k=0;k<=1;++k)
dp[i][j][k]=1e9;
dp[1][0][0]=dp[0][0][0]=0;
for(int i=1;i<=N;++i)
for(int j=0;j<=M;++j)
{
dp[i][j][0]=min(dp[i][j][0],min(dp[i-1][j][0]+Dist[Now[i-1]][Now[i]],dp[i-1][j][1]+Dist[Now[i-1]][Now[i]]*(1.0-p[i-1])+Dist[Oth[i-1]][Now[i]]*p[i-1]));
if(j>0) dp[i][j][1]=min(dp[i][j][1],min(dp[i-1][j-1][0]+Dist[Now[i-1]][Now[i]]*(1.0-p[i])+Dist[Now[i-1]][Oth[i]]*p[i],dp[i-1][j-1][1]+Dist[Oth[i-1]][Oth[i]]*p[i]*p[i-1]+Dist[Oth[i-1]][Now[i]]*p[i-1]*(1.0-p[i])+Dist[Now[i-1]][Oth[i]]*(1.0-p[i-1])*p[i]+Dist[Now[i-1]][Now[i]]*(1.0-p[i-1])*(1.0-p[i])));
}
double ans=1e9;
for(int i=0;i<=M;++i) ans=min(ans,min(dp[N][i][0],dp[N][i][1]));
printf("%.2lf",ans);
return 0;
}
|
有一个很贴切的事例：如果一个人被车创死的概率为 $p$ ，则两个人同时被车创死的概率就应该是 $p^2$ ，这是理所当然的。
所以，我们可以忽视条件 $k$ ，把 $k$ 只生物当做 $1$ 只来对待，然后转化成常规的概率 dp 即可。
对应有 $n$ 种情况，用 $dp[i]$ 表示第 $i$ 天死亡的概率，则有：
$dp[i]=\sum dp[i-1]^j\times p[j]$ ，其中 $p[j]$ 是这只生物变成 $j$ 只的概率。
而答案就是 $dp[M]^k$ 即可。
AC Code
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
| #include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
typedef long long ll;
using namespace std;
const int MAXN=1e3+1;
template<class T>
inline void read(T &x)
{
x=0;
char ch=gh(),t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
return x>y?x=y,1:0;
}
int Test,N,K,M;
double p[MAXN],dp[MAXN];
int main()
{
read(Test);
for(int Case=1;Case<=Test;++Case)
{
memset(dp,0,sizeof(dp));
memset(p,0,sizeof(p));
read(N,K,M);
for(int i=0;i<N;++i) scanf("%lf",&p[i]);
for(int i=1;i<=M;++i)
for(int j=0;j<N;++j)
dp[i]+=p[j]*pow(dp[i-1],j);
printf("Case #%d: %.7lf\n",Case,pow(dp[M],K));
}
return 0;
}
|
奖励关
矩阵加速 dp
字面意思，使用矩阵快速幂来优化动态规划已达到时间复杂度的限制。
例题
对于 $60\% $ 的做法：考虑首先求出 $a$ 与 $b$ 的所有重复元素，然后进行背包：
$f[i]=\sum f[i-j],j\ \text{合法}$
这样的复杂度大概是 $\mathcal O(100n)$ ，勉强能过。
但是对于 $n\le 10^{18}$ ，那真是异想天开。
考虑加速。无论如何，有 $0\le x\le 100$ ，则 $f[i]$ 最多是从 $f[i-100]\sim f[i-1]$ 转移而来的，那么考虑一个 $1\times Len$ 的矩阵（$len$ 表示最多能够转移的个数），然后考虑 $01$ 矩阵。使得：
计算出转移矩阵应该是：
即可。
答案矩阵的第 $1$ 行第 $1$ 列就是最终答案，时间复杂度 $\mathcal O(Len^3\log n)$
AC Code
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
| #include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
typedef long long ll;
using namespace std;
const int MAXL=101;
const int Mod=1e9+7;
template<class T>
inline void read(T &x)
{
x=0;
char ch=gh(),t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
return x>y?x=y,1:0;
}
ll Length;
int N,M;
int Len,Num[MAXL],dp[MAXL];
bool a[MAXL],b[MAXL];
struct Matrix
{
ll rix[MAXL][MAXL];
inline void clear()
{
memset(rix,0,sizeof(rix));
}
const Matrix operator*(Matrix b)const
{
Matrix c;
c.clear();
for(int i=1;i<=Len;++i)
for(int j=1;j<=Len;++j)
for(int l=1;l<=Len;++l)
c.rix[i][j]=(c.rix[i][j]+rix[i][l]*b.rix[l][j])%Mod;
return c;
}
}Zero,Ans;
inline Matrix qPow(Matrix s,ll b)
{
Matrix res;
res.clear();
for(int i=1;i<=Len;++i) res.rix[i][i]=1;
while(b)
{
if(b&1) res=res*s;
s=s*s;
b>>=1;
}
return res;
}
int main()
{
read(Length);
read(N);
for(int i=1,x;i<=N;++i) read(x),a[x]=1;
read(M);
for(int i=1,x;i<=M;++i) read(x),b[x]=1;
for(int i=1;i<=100;++i) if(a[i]&b[i]) Zero.rix[1][i]=1,Len=i;
for(int i=1;i<Len;++i) Zero.rix[i+1][i]=1;
dp[0]=1;
for(int i=1;i<=Len;++i)
for(int j=1;j<=i;++j)
if(a[j]&&b[j]) dp[i]=(dp[i]+dp[i-j])%Mod;
for(int i=1;i<=Len;++i) Ans.rix[i][1]=dp[Len-i];
Ans=qPow(Zero,Length-Len+1)*Ans;
printf("%lld",Ans.rix[1][1]);
return 0;
}
|
倍增 dp
例题
这道题是最短路径和倍增思想的结合题。
首先说一下一个明显的错误： 绝对不能直接求最短路。
原因很简单，题目中有说，有跑路器。
那么进一步思考，发现，任意 $2^k$ 的路径长度都可以在 $1$ 秒内走完，因此如果有 $u,v$ 两点间的最短距离为 $2^k$ 即可认为这两点之间有一条边（本题中边权全部为 $1$ ）。
接下来，思路就很简单了。令 $f_{i,j,k}$ 的意义为能否在 $2^i$ 时间内从点 $j$ 走到点 $k$ ，可以为 $1$ ，不可以为 $0$。进一步，由倍增的思想可以得到：若 $f_{i-1, v, k}$ 和 $f_{i-1, k, u}$ 同时为 $1$ ，则 $f_{i, v, u}$ 为 $1$ 。
在这些都预处理完成之后，在跑一个最短路，就正确了。
AC Code
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
| #include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define underMax(x,y) ((x)>(y)?(x):(y))
#define underMin(x,y) ((x)<(y)?(x):(y))
typedef long long LL;
using namespace std;
const int MAXN=101;
template<class T>
inline void underRead(T &x)
{
x=0;
char ch=gh(),t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();
if(t) x=-x;
}
bool G[MAXN][MAXN][MAXN];
int Dist[MAXN][MAXN],N,M,Qx,Qy;
int main()
{
underRead(N),underRead(M);
memset(Dist,0x3f,sizeof(Dist));
memset(G,0,sizeof(G));
for(int i=1;i<=M;++i)
{
underRead(Qx),underRead(Qy);
Dist[Qx][Qy]=1;G[Qx][Qy][0]=1;
}
for(int k=1;k<=64;++k)
{
for(int i=1;i<=N;++i)
{
for(int j=1;j<=N;++j)
{
for(int l=1;l<=N;++l)
{
if(G[i][j][k-1]&&G[j][l][k-1])
{
G[i][l][k]=1;
Dist[i][l]=1;
}
}
}
}
}
for(int k=1;k<=N;++k)
{
for(int i=1;i<=N;++i)
{
for(int j=1;j<=N;++j)
{
Dist[i][j]=underMin(Dist[i][j],Dist[i][k]+Dist[k][j]);
}
}
}
printf("%d",Dist[1][N]);
return 0;
}
|
数据结构优化 dp
线段树优化
这东西应该是最常见的数据结构优化（还有树状数组）了，将 $\mathcal O(n^2)$ 的 $\text{Dp}$ 转移优化到 $\mathcal O(n\log n)$ 。
对于一种转移：$Dp[i]=\max/\min(Dp[j]+calc(i,j)),1\leq j\leq i$ 的这种，暴力转移可以做到 $\mathcal O(n^2)$ ，但是我们可以用线段树来统计区间的最大的 $j$ 并转移，这样的复杂度查询只有 $\mathcal O(\log n)$ 。那么，此类的操作分为三步：查询，修改，上传。