设状态$f[i][j]$为从坐标$(i,j)$走到最后一行的期望

此时需要分类讨论,由于$f[n]j=0$，所以我们倒着枚举行,也可感性理解为从最后一行走到第x行

当$j=1$时，$f[i][1]=\frac{1}{3}f[i][1]+\frac{1}{3}f[i][2]+\frac{1}{3}f[i+1][1]+1$

当$j=m$时，$f[i][m]=\frac{1}{3}f[i][m]+\frac{1}{3}f[i][m-1]+\frac{1}{3}f[i+1][m]+1$

当$1<j<m$时，$f[i][j]=\frac{1}{4}f[i][j-1]+\frac{1}{4}f[i][j]+\frac{1}{4}f[i][j+1]+\frac{1}{4}f[i+1][j]+1$

然后我们发现这个式子是有后效性的，所以要$dp+$高斯消元。

为了更好高斯消元，我们可以压掉第一维，式子中的$f[i+1]$计为数组$last$。(但我实现上还是用了两维)

经过移项化简后得到：

当$j=1$时，$2f[1]-f[2]=last[i] + 3$

当$j=m$时，$-f[m-1]+2f[m]=last[m]+3$

当$1<j<m$时，$-f[j-1]+3f[j]-f[j+1]=last[j]+4$

由于是倒着枚举，所以$last$数组在转移前已经知道了，这就完全是个高斯消元的式子了，用矩阵表示就会变成下面这个样子

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

用高斯消元显然会T，但是我们发现每行最多只有$3$个非$0$元素,所以我们可以暴力模拟高斯消元求解,最后答案就是$f[x][y]$

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

#include <bits/stdc++.h>
#define mod 1000000007
#define ll long long
using namespace std;
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
double f[1007][1007],a1[1007],a2[1007],a3[1007],c[1007];
//c数组为方程组'='右边的值，a1,a2,a3分别表示一行中三个元素的值，f数组即为转移数组
signed main(){
    int n=read(),m=read(),x=read(),y=read();
    if (m==1){
        printf("%.10lf",2.0*(n-x));
        return 0;
    }
    for (int i=n-1;i>=x;--i){
        for (int j=1;j<=m;++j)c[j]=f[i+1][j]+4.0;
        c[1]-=1.0;c[m]-=1.0;
        a1[1]=0;a2[1]=2.0;a3[1]=-1.0;
        for (int j=2;j<=m-1;++j)a1[j]=-1,a2[j]=3,a3[j]=-1;
        a1[m]=-1;a2[m]=2;a3[m]=0;
        for (int j=2;j<=m;++j){
            double z=a1[j]/a2[j-1];
            a2[j]-=z*a3[j-1];
            c[j]-=c[j-1]*z;
        }
        f[i][m]=c[m]/a2[m];
        for (int j=m-1;j;--j)f[i][j]=(f[i][j+1]+c[j])/a2[j];
    }
    printf("%.10lf",f[x][y]);
}

$Description$

有$n$张符卡排成一个队列，每张符卡有两个属性，等级$l_{i}$和伤害$d_{i}$。
你可以做任意次操作，每次操作为以下二者之一：

$1$. 把队首的符卡移动到队尾。

$2$. 使用队首的符卡，对敌人造成$d_{i}$点伤害，并丢弃队首的$l_{i}$张符卡（包括你所使用的符卡）。如果队列不足$l_{i}$张符卡那么你不能使用。

求出造成的伤害的总和的最大值。

$1$$\leqslant$$n$$\leqslant$$50,1$$\leqslant$$l_{i}$$\leqslant$$50,1$$\leqslant$$d_{i}$$\leqslant$$10000$

有 $n$个点$,m $个操作，每次连接两个点，或者询问某两个点最早是在什么时刻开始连通的

给定一张有向图(可能有自环，保证没有重边)，每条边有两种类型，分别为$1$或者$0 $从$1$开始走，要求走过的路径类型成如下方式

$0$

$01$

$0110$

$01101001$

第$i$个是由第$i -1$个和第$i - 1$个取反拼在后面。 求最长路。

题意:给定$n$个$01$串，保证$01$串长度之和不超过$30000$，询问是否存在无限长的$01$串，使得给定串都不是它的子串。

$Description$

给定一个值$x$,一个长度为$n$的数组$a$，你可以选择一段区间，让这段区间每个数都乘上$x$,求最大连续子段和

题意：有$N$个点，$M$条双向边，$K$个被侵略城市，与这$K$个被侵略城市距离$\leqslant$$S$的城市就是危险城市。其他就是安全城市。安全城市的点权就是$P$，危险城市的点权就是$Q$,问才$1$号点到$N$号点的最小花费。

题意$:$给定一张 $n$个点$,m$条边的有重边的图，找到一个生成树，使得每条边的权值$ \times$到根的距离最小

基环树上$dp$

有$n$只兔子在一个数轴上，兔子为了方便起见从$ 1 $到$n $标号，第$ i $只兔子的初始坐标为$x_i$。兔子会以以下的方式在数轴上锻炼：一轮包含$m$个跳跃，第 $j$ 个是兔子$a[j] (2 \leqslant a[j] \leqslant N−1)$，$a$是给出的长度为$m$的数组跳一下，这一下从 兔子$a[j]− 1 $和 兔子$a[j] + 1$中等概率的选一个$（$假设选了$ x）$，那么$a[j]$号兔子 会跳到它当前坐标关于$x$的坐标的对称点。（注意，即使兔子的位置顺序变化了，但是编号仍保持不变，这里按兔子编号算）兔子会进行$k$轮跳跃，对每个兔子，请你求出它最后坐标的期望值。