題意:n*m的棋盤,一個機器人在(i,j)處,每次等概率地停在原地,向左移動一格,向右移動一格,向下移動一格(不能移出棋盤).求走到最后一行所需期望步數.n<=1000,m<=1000

一個看起來可以用來DP的順序是永遠只能從上面走到下面,但同一行之間的轉移會出現環.如果n和m的范圍稍微小一點,我們可以像SDOI走迷宮一題跑一個分層的高斯消元,但這個題的范圍比較大,會超時,但這道題的背景暗示我們列出來的方程組會比較規則,我們不妨先把方程列出來看看有什么特點.

設F[i][j]為從第i行第j列走到最后一行的期望步數

則有

F[i][1]=1+F[i][1]/3+F[i][2]/3+F[i+1]/3

F[i][j]=1+F[i][j]/4+F[i][j-1]/4+F[i][j+1]/4+F[i+1][j]/4,2<=j<=m-1

F[i][m]=1+F[i][m-1]/3+F[i+1][m]/3+F[i][m]/3

不妨仍考慮從第i+1行推到第i行.那么我們在求解F[i][1…m]的時候應當已經知道F[i+1][1…m],邊界顯然是F[n][j]=0

對于一行,有兩個方程只有兩個未知數,m-2個方程有三個未知數

如果兩個方程里面是同兩個未知數,我們可以直接解出這兩個未知數,但現在F[i][1]和F[i][m]的未知數并不一定是同兩個,我們可以考慮對這些式子進行變形.

F[i][1]的方程和F[i][1],F[i][2]有關,F[i][2]的方程和F[i][1],F[i][2],F[i][3]有關,那么我們可以用這兩個方程消掉F[i][1],得到關于F[i][2]和F[i][3]的二元一次方程,接下來再和F[i][3]的方程相消,可以得到關于F[i][3]和F[i][4]的方程….最終我們就可以解出最右端的F[i][m],此后順著推回來,復雜度O(n).

實現的時候我把每個二元一次方程表示成F[i][j]=a[j]*F[i][j+1]+b[j]的形式,比較容易理解.

轉移的式子可能需要簡單推一下,見代碼.

注意m=1的情況要特判.

#include<cstdio>
double f[1005][1005];
double a[1005],b[1005];
int main(){
  int n,m,x0,y0;scanf("%d%d%d%d",&n,&m,&x0,&y0);
  if(m==1){
    a[n]=0;
    for(int i=n-1;i>=x0;--i){
      a[i]=a[i+1]+2;
    }
    printf("%.4f
",a[x0]);
  }else{    
    for(int i=1;i<=m;++i)f[n][i]=0;
    for(int i=n-1;i>=x0;--i){
      a[1]=0.5;b[1]=f[i+1][1]/2+1.5;
      for(int j=2;j<m;++j){
    b[j]=b[j-1]/4.0+f[i+1][j]/4.0+1.0;
    a[j]=0.25;
    a[j]/=(0.75-a[j-1]/4.0);b[j]/=(0.75-a[j-1]/4.0);
      }
      f[i][m]=(b[m-1]+f[i+1][m]+3.0)/(2-a[m-1]);
      for(int j=m-1;j>=1;--j)f[i][j]=b[j]+a[j]*f[i][j+1];
    }
    printf("%.4f
",f[x0][y0]);
  }
  return 0;
}

總結

以上是生活随笔為你收集整理的CodeForces 24D Broken Robot的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。