来自lyd的书，给定一张N*M的棋盘和一个初始位置，机器人位于初始位置，每次等概率地选择停在原地，向左移动一格或者向下移动一格。不能移出棋盘，求机器人从初始位置走到最后一行的任意一个位置的数学期望。（1<=N,M<=1,000)。
注意很多数学期望DP都会采取倒推的方式进行我们记F[i][j]表示从(i,j)走到最后一行所需要的期望值
因为每一行内部可以相互转移，所以这个dp是有后效性的，但从下一行往上一行推的过程无后效性，对于行内有后效性的转移，使用高斯消元，将下一行已经得到的数据作为已知量。通过将这些方程移项可以推出很多方程组，将它们用矩阵表示，以M=5为例
观察后发现这种矩阵叫 三对角矩阵每一行消元只需要直接用下一行相邻的数据进行一次消元就行了，复杂度是线性的，加上每一行往上的无后效性递推，总体的复杂度是O(NM)。注意到M=1的时候要进行特殊处理，将第一个方程带入消元后发现每一行等于下一行的期望+2。在消元过程中很多细节的加加减减和系数处理都要在纸上列出算式消元后才能处理，要注意。
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
| double f[maxn],a[maxn][maxn],b[maxn];
int n,m,x,y;
void gauss()
{
for (int i=1;i<m;i++)
{
double rt=a[i+1][i]/a[i][i];
a[i+1][i]-=rt*a[i][i];
a[i+1][i+1]-=rt*a[i][i+1];
b[i+1]-=rt*b[i];
}
f[m]=b[m]/a[m][m];
for (int i=m-1;i>=1;i--)
{
f[i]=(b[i]-f[i+1]*a[i][i+1])/a[i][i];
}
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m>>x>>y;
if (m==1)
{
double ans= (double) (n-x) *2;
cout<<ans<<endl;
return 0;
}
for (int i=n-1;i>=x;i--)
{
a[1][1]=(double)-2/3;
a[1][2]=(double)1/3;
a[m][m-1]=(double)1/3;
a[m][m]=(double)-2/3;
b[1]=(double)((double)-1/3)*f[1]-1;
b[m]=(double)((double)-1/3)*f[m]-1;
for (int j=2;j<m;j++)
{
a[j][j-1]=a[j][j+1]=(double)1/4;
a[j][j]=(double)-3/4;
b[j]=(double)((double)-1/4)*f[j]-1;
}
gauss();
}
cout<<setprecision(10)<<f[y]<<endl;
return 0;
}
|
