1 条题解

  • 0
    @ 2025-10-8 16:56:30
    #include <iostream>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    const int N=1010;
    double a[N][N],f[N];
    int n,m,st,ed;
    
    void solve(){
      for(int k=n-1; k>=st; k--){
        memset(a,0,sizeof a);
        for(int i=1; i<=m; i++){
          if(i==1){
            a[i][i]=2;
            a[i][i+1]=-1;
            a[i][m+1]=3+f[i];
            continue;
          } 
          else if(i==m){
            a[i][i]=2;
            a[i][i-1]=-1;
            a[i][m+1]=3+f[i];
            continue;
          }
          a[i][i]=3;
          a[i][i+1]=-1;
          a[i][i-1]=-1;
          a[i][m+1]=4+f[i];
        }
        
        for(int i=1; i<m; i++){
          double p=a[i+1][i]/a[i][i];
          a[i+1][i]=0;
          a[i+1][i+1]-=a[i][i+1]*p;
          a[i+1][m+1]-=a[i][m+1]*p;
        }
        f[m]=a[m][m+1]/a[m][m];
        for(int i=m-1; i>=1; i--)
          f[i]=(a[i][m+1]-f[i+1]*a[i][i+1])/a[i][i];
      }
    }
    int main(){
      scanf("%d %d",&n,&m);
      scanf("%d %d",&st,&ed);
      if(m==1){
        printf("%.10f\n",2.0*(n-st)); return 0;
      }
      solve();
      printf("%.10f\n",f[ed]);
    }
    
    • 1

    E42_2 *【概率DP:求期望 高斯消元】[CF24D] Broken robot

    信息

    ID
    1342
    时间
    2000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    24
    已通过
    14
    上传者