codeforces24D

CF24D Broken robot

题目背景

小小迪带你吃瓜

题目描述

给出一个 n×m 的矩阵区域，一个机器人初始在第 x 行第 y 列，每一步机器人会等概率的选择停在原地，左移一步，右移一步，下移一步，如果机器人在边界则丌会往区域外移动，问机器人到达最后一行的期望步数。

输入输出格式

输入格式：

第一行两个整数，分别表示 n 和 m。第二行两个整数，分别表示 x 和 y

输出格式：

一个小数表示答案

输入输出样例

输入样例#1：

10 10
10 4

输出样例#1：

0.0000000000

输入样例#2：

10 14
5 14

输出样例#2：

18.0038068653

sol：肯定是dp辣，状态呼之欲出了，dp[i][j]表示从位置i，j到最后一行的期望步数
转移也十分容易（但是不能直接转移，因为是几个方程组，要用高斯消元解出来）
前面带-->表示这是用来消元的方程

dp[i][1]=1/3*(dp[i][1]+dp[i][2]+dp[i+1][1])+1 (1)
--> dp[i][1] - 1/3*dp[i][1] - 1/3*dp[i][2] = 1/3*dp[i+1][1]+1
dp[i][j]=1/4*(dp[i][j]+dp[i][j-1]+dp[i][j+1]+dp[i+1][j])+1 (2~m-1)
--> dp[i][j] - 1/4*dp[i][j] - 1/4*dp[i][j-1] - 1/4*dp[i][j+1] = 1/4*dp[i+1][j]+1
dp[i][m]=1/3*(dp[i][m]+dp[i][m-1]+dp[i+1][m])+1 (m)
--> dp[i][m]-1/3*dp[i][m]-1/3*dp[i][m-1] = 1/3*dp[i+1][m]+1

但是直接解是n³的，会T出屎，但是这个每行最多就3个不为0的系数，所以O(n)推过去，求出最后一个，在推回来即可

/*
dp[i][1]=1/3*(dp[i][1]+dp[i][2]+dp[i+1][1])+1 (1)
--> dp[i][1] - 1/3*dp[i][1] - 1/3*dp[i][2] = 1/3*dp[i+1][1]+1
dp[i][j]=1/4*(dp[i][j]+dp[i][j-1]+dp[i][j+1]+dp[i+1][j])+1 (2~m-1)
--> dp[i][j] - 1/4*dp[i][j] - 1/4*dp[i][j-1] - 1/4*dp[i][j+1] = 1/4*dp[i+1][j]+1
dp[i][m]=1/3*(dp[i][m]+dp[i][m-1]+dp[i+1][m])+1 (m)
--> dp[i][m]-1/3*dp[i][m]-1/3*dp[i][m-1] = 1/3*dp[i+1][m]+1
*/
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
inline ll read()
{
    ll s=0;
    bool f=0;
    char ch=' ';
    while(!isdigit(ch))
    {
        f|=(ch=='-'); ch=getchar();
    }
    while(isdigit(ch))
    {
        s=(s<<3)+(s<<1)+(ch^48); ch=getchar();
    }
    return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
    if(x<0)
    {
        putchar('-'); x=-x;
    }
    if(x<10)
    {
        putchar(x+'0');    return;
    }
    write(x/10);
    putchar((x%10)+'0');
    return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('
')
const int N=1005;
int X,Y;
double dp[N][N];
double a[N][N],b[N];
inline void Debug(int n)
{
    int i,j;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++) printf("%.3lf ",a[i][j]);
        printf("%.3lf
",b[i]);
    }
}
inline void Gauss(int n)
{
    int i;
    double Div;
    // Debug(n);
    for(i=1;i<=n;i++)
    {
        double Div=a[i][i];
        a[i][i]/=Div; b[i]/=Div;
        if(i==n) break;
        a[i][i+1]/=Div;
        Div=a[i+1][i]/a[i][i];
        a[i+1][i]-=Div*a[i][i];
        a[i+1][i+1]-=Div*a[i][i+1];
        b[i+1]-=Div*b[i];
    }
    for(i=n-1;i>=1;i--) b[i]-=b[i+1]*a[i][i+1];
}
int main()
{
    int i,j,n,m;
    R(n); R(m); R(X); R(Y);
    for(i=1;i<=m;i++) dp[n][i]=0.;
    for(i=n-1;i>=X;i--)
    {
        if(m!=1)
        {
            a[1][1]=2./3.; a[1][2]=-1./3.; b[1]=1./3.*dp[i+1][1]+1.;
        }
        else
        {
            a[1][1]=1./2.; b[1]=1./2.*dp[i+1][1]+1;
        }
        for(j=2;j<m;j++)
        {
            a[j][j]=3./4.; a[j][j-1]=-1./4.; a[j][j+1]=-1./4.; b[j]=1./4.*dp[i+1][j]+1.;
        }
        if(m>1)
        {
            a[m][m]=2./3.; a[m][m-1]=-1./3.; b[m]=1./3.*dp[i+1][m]+1.;
        }
        Gauss(m);
        for(j=1;j<=m;j++) dp[i][j]=b[j];
    }
    printf("%.10lf
",dp[X][Y]);
    return 0;
}
/*
input
10 10
10 4
output
0.0000000000

input
10 14
5 14
output
18.0038068653

input
2 1
1 1
output
2.0000000000
*/

View Code