Snakes and Ladders LightOJ - 1151
题意：
有100个格子，从1开始走，每次抛骰子走1~6，若抛出的点数导致走出了100以外，则重新抛一次。有n个格子会单向传送到其他格子，tp[i]表示从i传送到tp[i]。
1和100不会有传送，一个格子也不会有两种传送。问走到100的期望值。
\(dp[i]\)表示从格子i走出去的期望次数
分两种情况考虑
格子不可以传送 \(dp[i] = \frac{1}{6} \cdot \sum_{j=1}^{k}dp[i+j] + \frac{1}{6} \cdot \sum_{j=k+1}^{6}dp[i] + 1 (i+k=100)\)
格子可以传送 \(dp[i] = dp[nxt[i]]\)
化简得
格子不可以传送 \(k \cdot dp[i] - \sum_{j=1}^{k}dp[i+j] = 6\)
格子可以传送 \(dp[i] = dp[nxt[i]]\)
由于传送是无序的，所以无法使用递推来解决，只能列矩阵方程来高斯消元
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const double eps = 1e-6;
const int N = 110;
int nxt[N];
double a[N][N];
int gauss(int n,int m){
int col,i,mxr,j,row;
for(row=col=1;row<=n&&col<=m;row++,col++){
mxr = row;
for(i=row+1;i<=n;i++)
if(fabs(a[i][col])>fabs(a[mxr][col]))
mxr = i;
if(mxr != row) swap(a[row],a[mxr]);
if(fabs(a[row][col]) < eps){
row--;
continue;
}
for(i=1;i<=n;i++)///消成上三角矩阵
if(i!=row&&fabs(a[i][col])>eps)
for(j=m;j>=col;j--)
a[i][j]-=a[row][j]/a[row][col]*a[i][col];
}
row--;
for(int i = row;i>=1;i--){///回代成对角矩阵
for(int j = i + 1;j <= row;j++){
a[i][m] -= a[j][m] * a[i][j];
}
a[i][m] /= a[i][i];
}
return row;
}
int main()
{
int T, cas = 1;
cin>>T;
while(T--){
int n;
scanf("%d",&n);
memset(nxt, 0, sizeof(nxt));
for(int i = 0;i < n;i++){
int x , y;
scanf("%d%d",&x,&y);
nxt[x] = y;
}
printf("Case %d: ",cas++);
memset(a, 0, sizeof(a));
for(int i = 1;i < 100;i++){
if(nxt[i]){
a[i][101] = 0;
a[i][i] = 1,a[i][nxt[i]] = -1;
}else{
int cnt = 0;
for(int j = 1;i + j <= 100 && j <= 6;j++){
cnt++;
a[i][i+j] = -1;
}
a[i][i] = cnt,a[i][101] = 6;
}
}
a[100][100] = 1,a[100][101] = 0;
int row = gauss(100,101);
printf("%.12lf\n",a[1][101]);
}
return 0;
}