做题笔记：CF24D

ShanQing · 2022-12-30 21:03:34 · 个人记录

更好的阅读体验

这是一道高斯消元+简单期望DP的好题，有人说这是道算黑题的紫题

刚开始也是卡在了高斯消元优化这一步，所以查了一些资料，调了一个小时的代码后终于A掉了

这道题对我启发巨大，所以来写一篇做题笔记，想做或正在做此题的人也可以当作不发布的民间题解

正文开始

luogu题面戳这

CF原题面戳这

理解题意

有一个n行m列的矩阵，有一个机器人原在矩阵方格(x,y)处，每次等概率进行以下操作，但不能出边界，分别是向左，右，下方移动一个单位，以及不动，问移动到最后一行（即第n行）的期望

只要知道期望是什么意思，即使刚入门的Oier也很好理解题意，不再赘述附：期望的概念

思路分析

毕竟此题有一部分是期望DP，所以肯定要推每个方格的状态转移方程

设f[i][j]表示从方格坐标(i,j)处移到第n行的期望值

可以很轻易地推出状态转移方程：

首先当i=n时，即处于最后一行，废话什么，当然全部是0

然后考虑三种情况：

当j=1时，即处于最左边，此时可以从自己，右边，下边转移过来

所以方程为：

f[i][1]=\frac{f[i][1]+f[i][2]+f[i+1][1]}{3}+1

同理，当j=m时，此时在最右边，可以从自己，左边，下边转移过来

方程为：

f[i][m]=\frac{f[i][m]+f[i][m-1]+f[i+1][m]}{3}+1

还有一种情况大家肯定想得到，就是j\ne 1,j\ne m，即不在最左边，也不在最右边，左，右，下都有方格

此时自己，左边，右边，下边都可以进行转移

显而易见这时候方程长这样：

f[i][j]=\frac{f[i][j]+f[i][j-1]+f[i][j+1]+f[i+1][j]}{4}+1

这时候就能快乐的进行转移了......

相信注意到了，这个方程和以往的DP不太一样，这关系之间怎么有环?

别急，这题不是还有一个标签吗？高斯消元

建立消元矩阵

我们先将三个方程移项了，将f[i+1][j]和+1留在方程右边，其它，统统移过去

第一个方程(j=1)可变为:

\frac{2}{3}f[i][1]-\frac{1}{3}f[i][2]=\frac{1}{3}f[i+1][1]+1

第二个方程(j=m)可变为：

-\frac{1}{3}f[i][m-1]+\frac{2}{3}f[i][m]=\frac{1}{3}f[i+1][m]+1

第三个方程(j\ne 1,j\ne m)可变为：

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

现在，如果我们把f[i+1][j]当作已知数的话，就可以显而易见列出矩阵：

\begin{bmatrix}\frac{2}{3}&-\frac{1}{3}&0&0&0&|&\frac{1}{3}f[i+1][j]+1\\-\frac{1}{4}&\frac{3}{4}&-\frac{1}{4}&0&0&|&\frac{1}{4}f[i+1][j]+1\\0&-\frac{1}{4}&\frac{3}{4}&-\frac{1}{4}&0&|&\frac{1}{4}f[i+1][j]+1\\0&0&-\frac{1}{4}&\frac{3}{4}&-\frac{1}{4}&|&\frac{1}{4}f[i+1][j]+1\\0&0&0&-\frac{1}{3}&\frac{2}{3}&|&\frac{1}{3}f[i+1][j]+1\end{bmatrix}

~~写矩阵真的太累了~~

对于如何求f[i+1][j]使矩阵右边变成已知数，我们不妨从第n-1行倒推到第x行，依次求出每一行所有数的f值就行，再将第i行的结果用于第i-1行的求解

所以思路已经很明显了，从n-1行倒推，对每行进行一次高斯消元求出当前行的所有f值，再用于上面一行的求解，直到第x行

关于高斯消元部分(本题妙点，敲黑板敲黑板)

...你看直接对每行用裸的高斯消元的话复杂度是O(nm^2)，而这题n,m达到了10^3级别，岂不是起飞了(

所以需要对裸的高斯消元优化

再次观察矩阵，发现这个矩阵有规律：第1行和第m行 (即最后一行) 只有两个非0数，另外2至m-1每行有三个，其他部分则构成了两个全0的上三角和下三角

所以我们可以在枚举矩阵每一行时直接选取当前行，同时只削掉下一行的三个数，得到了一个这样的矩阵(非0数在这里设为1）

\begin{bmatrix}1&1&0&0&0&|&1\\0&1&1&0&0&|&1\\0&0&1&1&0&|&1\\0&0&0&1&1&|&1\\0&0&0&0&1&|&1\end{bmatrix}

我们惊奇地发现：

现在只要从最后一行往上反推，就能求出所有答案！

我们顺利地将算法优化到了O(nm)，显然已经是本题正解了

...吗？

特判

这题还有一个细节叫特判

上面推式子时还没讲，特地放在这里强调

想一下，如果m=1呢？

此时只能向下移动，每一个方格的状态转移方程变为：

f[i][1]=\frac{f[i+1][1]+f[i][1]}{2}+1

将它转换一下，易得：

f[i][1]=f[i+1][1]+2

显然这时又可以直接推出第i行第n行的关系了：

f[i][1]=f[n][1]+2\times (n-x)

由于第n行的f值全部为0，所以此时2\times (n-x)就是答案，特判输出即可

终于可以快乐地码它了)

code

#include <bits/stdc++.h>
using namespace std;
int n,m,x,y;
double f[1005][1005],a[1005][1005];
//f的意义同上，a是每一行的消元矩阵 
void gauss()
{
    for(int i=1;i<=m;++i)
    {
        double r=a[i][i];
        a[i][i]/=r,a[i][i+1]/=r;
        if(i<m) a[i][m+1]/=r;
        double t=a[i+1][i];
        int d[3]={i,i+1,m+1};
        for(int j=0;j<3;++j)
        {
            a[i+1][d[j]]-=t*a[i][d[j]];
        }
    }//消元 
    for(int i=m;i;--i)
    {
        a[i-1][m+1]-=a[i-1][i]*a[i][m+1];
        a[i-1][i]-=a[i-1][i]*a[i][i];
    }//倒推 
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&x,&y);
    if(m==1) printf("%.10lf\n",(double)(2*(n-x)));//注意特判！ 
    else
    {
        for(int i=n-1;i>=x;--i)
        {
            a[1][1]=2.0/3,a[1][2]=-1.0/3,a[1][m+1]=f[i+1][1]/3+1;
            a[m][m]=2.0/3,a[m][m-1]=-1.0/3,a[m][m+1]=f[i+1][m]/3+1;
            //处理第i行消元矩阵的第1，m行 
            for(int j=2;j<m;++j)
            {
                a[j][j-1]=-1.0/4,a[j][j]=3.0/4,a[j][j+1]=-1.0/4;
                a[j][m+1]=f[i+1][j]/4+1;
            }//处理第i行消元矩阵的第2至m-1行
            gauss();
            for(int j=1;j<=m;++j)
            {
                f[i][j]=a[j][m+1];
            }//转移答案 
        }
        printf("%.10lf\n",f[x][y]);
    }
    return 0;
}