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\) 个按钮。