概率期望

andyl / 2023-09-05 / 原文

Broken robot

设 $f[i][j]$ 表示从 $(i,j)$ 到最后一行的期望步数。

状态转移方程：

\[f[i][j]=\begin{cases}\frac{1}{4}(f[i][j]+f[i][j-1]+f[i][j+1]+f[i+1][j])+1\qquad(2\le j\le m)\\\frac{1}{3}(f[i][j]+f[i][j+1]+f[i+1][j])+1\qquad (j=1)\\\frac{1}{3}(f[i][j]+f[i][j-1]+f[i+1][j])+1\qquad(j=m)\\\end{cases} \]

初始条件：$f[n][j]=0$

然后发现这个状态转移方程有后效性，无法直接转移，所以考虑高斯消元。

因为第 $i$ 行的状态只能由第 $i+1$ 行得到，所以可以考虑先求出 $f[i+1][1\sim m]$ 的数值，再通过高斯消元求出 $f[i][1\sim m]$ 的值。

当$2\le j\le m$时，有：

\[3f[i][j]-f[i][j-1]-f[i][j+1]=4+f[i+1][j] \]

当$j=1$时，有：

\[2f[i][j]-f[i][j+1]=3+f[i+1][j] \]

当$j=m$时，有：

\[2f[i][j]-f[i][j-1]=3+f[i+1][j] \]

然后我们的系数矩阵长这样：

\[\begin{bmatrix} 2 & -1 & 0 & 0 & 0 & 0\\ -1 & 3 & -1 & 0 & 0 & 0\\ 0 & -1 & 3 & -1 & 0 & 0\\ 0 & 0 & -1 & 3 & -1 & 0\\ 0 & 0 & 0 & -1 & 3 & -1\\ 0 & 0 & 0 & 0 & -1 & 2\\ \end{bmatrix} \]

消元时，先把每列最靠下的 $-1$ 消完，变成上三角矩阵，然后把每列最靠上的 $-1$ 消完，就能得到最终结果。

$code:$

int main(){
	scanf("%lld%lld%lld%lld",&n,&m,&x,&y);
	if(m==1){
		printf("%lld.0000\n",(n-x)*2);
		return 0;
	}
	for(int i=n-1;i>=1;--i){
		h[1][1]=2;h[1][2]=-1;h[1][3]=3+f[i+1][1];//系数矩阵第一行
		for(int j=2;j<=m-1;++j){
			h[j][1]=3-h[j-1][2]*(-1)/h[j-1][1];//中间的那个数
			h[j][2]=-1;//最右边的那个数
			h[j][3]=f[i+1][j]+4-h[j-1][3]*(-1)/h[j-1][1];//等式右侧的常数
		}
		h[m][1]=-1;
		h[m][2]=2-h[m-1][2]*h[m][1]/h[m-1][1];
		h[m][3]=3+f[i+1][m]-h[m-1][3]*h[m][1]/h[m-1][1];//最后一行
		f[i][m]=h[m][3]/h[m][2];
		for(int j=m-1;j>=2;--j){
			f[i][j]=(h[j][3]-f[i][j+1]*h[j][2])/h[j][1];
		}
		f[i][1]=(h[1][3]-f[i][2]*h[1][2])/h[1][1];
	}
	printf("%.7lf\n",f[x][y]);
	return 0;
}

P3750 [六省联考 2017] 分手是祝愿

根据题意可以发现两个性质：①：任意一个按钮不能被其他组合按钮替代；②：最优策略下，任意一个按钮最多只能按一次。所以考虑倒序扫描序列，每发现一个 $1$ ，就按下它，并更新它的约数。这样就能找到最优策略下，哪些按钮必须要按，并设按钮的数量为 $cnt$ 。然后就能 $dp$ 了，设 $f[i]$ 表示在随意按键的情况下，从剩余 $i$ 个按钮到剩余 $i-1$ 个按钮的期望操作次数。状态转移方程：

\[f[i]=\frac{i}{n}+\frac{n-i}{n}\times (f[i]+f[i+1]+1) \]

含义：

按一次有 $\frac{i}{n}$ 的概率成功按到那 $i$ 个按钮，有 $\frac{n-i}{n}$ 的概率失败，错误地按到其他按钮。如果失败，那么错按的那个按钮还得按回来，然后再从 $i$ 个按钮按到 $i-1$ 个按钮。