有100个格子，从1开始走，每次抛骰子走1~6，若抛出的点数导致走出了100以外，则重新抛一次。有n个格子会单向传送到其他格子，G[i]表示从i传送到G[i]。
1和100不会有传送，一个格子也不会有两种传送。问走到100的期望值。
我们不难推出方程 但是由于dp值之间的前后影响 我们需要用高斯消元来解决
#include <bits/stdc++.h> #define ll long long #define inf 0x3f3f3f3f using namespace std; const int N = 1e5+7; const double eps = 1e-8; int G[107]; double A[207][107],x[107];//A矩阵中每一行1~n存系数，n+1为答案，m个方程m行，x是最终的答案 //注意空间要多开几个，还要考虑n，m不同的情况 int Guass(int n,int m)//有n个未知数，m个方程 { int i=1,j=1,k,r,c; while(i<=m && j<=n)//正在处理第i个方程，解第j个未知数 { r=i;//找到绝对值最大的系数，防止除数为0的情况，使得其他方程组系数不会变得太大 for(k=i+1;k<=m;k++)if(fabs(A[k][j])>fabs(A[r][j]))r=k; if(fabs(A[r][j])>=eps)//出现为0的情况，说明此项已经被消掉了，直接用进行下一个未知数，而方程不变,不过这个时候，一般来说跳过的这个元素就没有固定解啦 { for(c=1;c<=n+1;c++)swap(A[i][c],A[r][c]);//交换 for(k=i+1;k<=m;k++)if(fabs(A[k][j])>=eps) { double f=A[k][j]/A[i][j]; for(c=j;c<=n+1;c++)//当前方程j前面的系数都是0 A[k][c]-=f*A[i][c]; } i++;//获取下一个方程 } j++;//去消下一个未知数 } //必须先判无解再判断多解 for(k=i;k<=m;k++)if(fabs(A[k][n+1])>=eps)return 0;//若有一行系数为0但是不为答案，则无解 if(i<=n)return 2;//如果被你处理出来的方程没有n个，就会出现多解。(i=n表示解决了n-1个方程) for(int i=n;i>=1;i--) { for(j=i+1;j<=n;j++) A[i][n+1]-=A[i][j]*x[j]; x[i]=A[i][n+1]/A[i][i]; } //最终统计出来的答案x[i]肯定是对应的第i个元素的解哦,换的只是方程的顺序 return 1;//拥有唯一解 } int main(){ // ios::sync_with_stdio(false); // cin.tie(0); int t; scanf("%d",&t); int w=0; while(t--){ memset(G,0,sizeof(G)); memset(A,0,sizeof(A)); memset(x,0,sizeof(x)); int n; scanf("%d",&n); for(int i=1;i<=n;i++){ int a,b; scanf("%d%d",&a,&b); G[a]=b; } A[100][100]=1; A[100][101]=0; for(int i=1;i<=99;i++){ if(G[i]){ A[i][i]=1; A[i][G[i]]=-1; A[i][101]=0; }else{ int top=min(6,100-i); for(int j=1;j<=top;j++){ A[i][i+j]=-1; } A[i][i]=top; A[i][101]=6; } } Guass(100,101); printf("Case %d: %.10f\n",++w,x[1]); } }