概率高消light oj 1151

t个样例

n个楼梯或蛇;

a b

刚好走到a会到b;

问走到100期望;

dp[i] i到100的期望

这一点没奇怪的东西 dp[i]=1/6(dp[i+1]+dp[i+2]..+6);

有 dp[i]=dp[tp[i]];

6*dp[i]-dp[i+1]...=6;

dp[i]-dp[tp[i]]=0;

方程然后消一下

  1 #include<stdio.h>
  2 #include<algorithm>
  3 #include<string.h>
  4 #include<math.h>
  5 
  6 using namespace std;
  7 
  8 int p[200];
  9 double a[200][200];
 10 double x[200]; 解
 11 bool free_x[200];
 12 #define esp  1e-8
 13 
 14 int Gauss(int r,int c)
 15 {
 16     for(int i=1;i<=c;i++)
 17     {
 18         x[i]=0;
 19         free_x[i]=true;        
 20     }
 21     int  col=1,k;
 22 
 23     for(k=1;k<=r&&col<c;k++,col++)
 24     {
 25         int mar=k;
 26         for(int i=k+1;i<=r;i++)
 27         {
 28             if(fabs(a[i][col])>fabs(a[mar][col]))
 29                 mar=i;
 30         }
 31         if(mar!=k)
 32             for(int j=k;j<=c;j++)
 33             {
 34                 double tmp=a[k][j];
 35                 a[k][j]=a[mar][j];
 36                 a[mar][j]=tmp;
 37             }
 38         if(fabs(a[k][col])<esp)
 39         {
 40             k--;
 41             continue;
 42         }
 43         for(int i=k+1;i<=r;i++)
 44             if(fabs(a[i][col])>esp)
 45             {
 46                 double tmp=a[i][col]/a[mar][col];
 47                 for(int j=col;j<=c;j++)
 48                     a[i][j]-=a[k][j]*tmp;
 49             }
 50     }
 51     for(int i=k;i<=r;i++)
 52         if(fabs(a[i][c])>esp)
 53             return 0;
 54     for(int i=c-1;i>=1;i--)
 55     {
 56         double tmp=a[i][c];
 57         for(int j=i+1;j<c;j++)
 58             if(fabs(a[i][j])>esp)
 59                 tmp-=x[j]*a[i][j];
 60         x[i]=tmp/a[i][i];
 61     }
 62     return 1;
 63 }
 64 int main()
 65 {
 66     int t,ca;
 67     scanf("%d",&t);
 68     ca=1;
 69 
 70     while(t--)
 71     {
 72         for(int i=1;i<=100;i++)
 73             p[i]=i;
 74         int n;
 75         scanf("%d",&n);
 76         for(int i=1;i<=n;i++)
 77         {
 78             int a,b;
 79             scanf("%d%d",&a,&b);
 80             p[a]=b;
 81         }
 82         memset(a,0,sizeof(a));
 83         a[100][100]=1;  //这边构造一下 x[100]=0;
 84         a[100][101]=0;
 85         for(int i=1;i<100;i++)
 86         {
 87             if(p[i]==i)
 88             {
 89                 int k=0;
 90                 for(int j=i+1;j<=100&&j<=i+6;j++)
 91                 {
 92                     a[i][j]-=1;
 93                     k++;
 94                 }
 95                 a[i][i]+=k;
 96                 a[i][101]+=6;
 97             }
 98             else
 99             {
100                 a[i][i]+=1;
101                 a[i][p[i]]-=1;    
102             }            
103         }
104         Gauss(100,101);
105         printf("Case %d: %.8lf
",ca++,x[1]);        
106     }
107 
108     return 0;
109 }

概率 高消light oj 1151

概率高消light oj 1151