Snakes and Ladders(简单高斯消元)

Snakes and Ladders

格子的转移可以往前也可以往后,很容易想到高斯消元

当本格子可以转移到其他各自格子,很简单,$dp[i]=dp[nx{t}_i]$

否则,易得$dp[i]=1+\frac{1}{6}\sum _{j=1}^{k}dp[i+k]+\frac{1}{6}\sum _{k+1}^{6}dp[i]$

化简可得到

$k\ast dp[i]-\sum _{i=1}^{k}dp[i+k]=6$

所以统计$k$即可,就是统计最大的$i+k<=100$的那个点

#include <bits/stdc++.h> using namespace std; const int maxn=109; double mp[109][109],ans[maxn]; int ok1[maxn],ok2[maxn]; void guess(int n)//第n列是等式的右边 { for(int i=1;i<=n;i++)//现在开始消除i列 { int r=i;//记录系数最大的 for(int j=i+1;j<=n;j++) if( fabs( mp[r][i] )<fabs( mp[j][i] ) ) r=j; if( i!=r ) swap( mp[i],mp[r] );//把系数最大的换到当前行 double div = mp[i][i]; for(int j=i;j<=n+1;j++) mp[i][j]/=div; for(int j=i+1;j<=n;j++)//开始消元 { div = mp[j][i]; for(int k=i;k<=n+1;k++) mp[j][k]-=mp[i][k]*div; } } ans[n] = mp[n][n+1]; for(int i=n-1;i>=1;i--) { ans[i]=mp[i][n+1]; for(int j=i+1;j<=n;j++) ans[i]-=mp[i][j]*ans[j];//i之后的解出来了,那么减掉 } } int main() { int t,casenum=0; cin >> t; while( t-- ) { int n; cin >> n; memset(ok1,0,sizeof(ok1)); memset(ok2,0,sizeof(ok2)); memset(mp,0,sizeof(mp)); for(int i=1;i<=n;i++) { int l,r; cin >> l >> r; if( r>l ) ok1[l]=r;//前进 else ok2[l]=r;//倒退 } for(int i=1;i<=100;i++) { if( ok1[i] )//前进 { mp[i][i]=1; mp[i][ok1[i]]=-1.0; continue; } else if( ok2[i] )//后退 { mp[i][i]=1; mp[i][ok2[i]]=-1.0; continue; } int cnt=0; for(int j=1;i+j<=100&&j<=6;j++) cnt++,mp[i][i+j]=-1; mp[i][i]=cnt,mp[i][101]=6; } mp[100][100] = 1, mp[100][101] = 0; guess(100); printf("Case %d: %.10lf\n",++casenum,ans[1]); } }