概率dp专场

2022-08-22 08:09:03

概率dp专场

专题链接

第一题--poj3744 Scout YYF I  链接 （简单题）

算是递推题 如果直接推的话 会TLE 会发现 在两个长距离陷阱中间 很长一部分都是重复的 我用 a表示到达i-2步的概率 b表示到达i-1步的概率 c表示到达i步的概率

如果数很大的话 中间肯定会有重复的a,b,c 直接将i挪到最近的陷阱前一位 i = a[o]-1，大大节省时间。

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 using namespace std;

 #define LL long long

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 int x[];

 int main()

 {

     int i,n,j;

     double p;

     while(cin>>n)

     {

         cin>>p;

         for(i =  ;i < n ;i++)

         {

             cin>>x[i];

         }

         sort(x,x+n);

         double a = 1.0,b=0.0,c;

         double ta = ,tb = ;

         int o = ;

         if(x[]==)

         a = ;

         else a = ;

         for(i = ; i <= x[n-]+ ; i++)

         {

             if(i==x[o])

             {

                 o++;

                 while(x[o]==x[o-])

                 o++;

                 c = ;

             }

             else

             c = a*p+b*(1.0-p);

             b = a;

             a = c;

             if(o<n&&fabs(ta-a)<eps&&fabs(tb-b)<eps)

             i = x[o]-;

             ta = a;

             tb = b;

         }

         printf("%.7f\n",c);

     }

     return ;

 }

第二题--poj3071Football(简单题）

dp[i][j] 表示第i场j赢的概率 那么可以写出方程dp[i][j] += dp[i-1][g]*p[j][g].

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 using namespace std;

 #define N 100000

 #define LL long long

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 double p[][];

 double dp[][];

 int pp[];

 int main()

 {

     int i,j,n,g;

     pp[] = ;

     for(i =  ;i <=  ;i++)

     pp[i] = pp[i-]*;

     while(cin>>n)

     {

         if(n==-) break;

         memset(dp,0.0,sizeof(dp));

         int k = n;

         n = pp[n];

         for(i = ; i <=n ; i++)

             for(j =  ;j <= n; j++)

             cin>>p[i][j];

         for(i = ; i <=n ;i++)

         {

             if(i%)

             dp[][i] = p[i][i+];

             else

             dp[][i] = p[i][i-];

         }

         for(i =  ;i <= k ;i++)

         {

             for(j =  ;j <= n ;j+=pp[i])

             {

                 for(g = j; g < j+pp[i-] ; g++)

                 {

                     for(int e = j+pp[i-] ; e < j+pp[i] ; e++)

                     {

                         dp[i][g]+=dp[i-][g]*dp[i-][e]*p[g][e];

                         dp[i][e]+=dp[i-][e]*dp[i-][g]*p[e][g];

                     }

                 }

             }

         }

         double maxz = ;

         int ans;

         for(i = ; i <= n ;i++)

         {

             if(maxz<dp[k][i])

             {

                 maxz = dp[k][i];

                 ans = i;

             }

             //printf("%.5lf %d\n",dp[k][i],i);

         }

         cout<<ans<<endl;

     }

     return ;

 }

第三题--CodeForces 148D(简单题）

刚开始看错了题意，以为一次跳出一个老鼠，按概率直接算，WA后发现dragon画的时候会另有一只跳出来，这样就根据跳出来的是黑还是白分两种情况计算。

如果当前是dragon轮 也就是（总数-剩余数）%3！=0 时  dp[i][j] = j/(i+j)*((j-1)/(i+j-1)*dp[i][j-2]+i/(i+j-1)*dp[i-1][j-1])

dp[i][j] 表示还有i只白老鼠及j只黑老鼠时princess赢的概率。 princess轮计算方式类似。

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 using namespace std;

 #define N 1010

 #define LL long long

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 double dp[N][N];

 int main()

 {

     int i,a,b,j;

     while(cin>>a>>b)

     {

         memset(dp,,sizeof(dp));

         for(i =  ;i <= a ; i++)

         {

             if((a+b-i)%==)

             dp[i][] = ;

         }

         for(i =  ; i <= a ;i++)

             for(j =  ;j <= b ;j++)

             {

                 if((a+b-(i+j))%)

                 {

                     if(j>=)

                     dp[i][j] = j*1.0/(i+j)*((j-)*1.0/(i+j-)*dp[i][j-]+(i*1.0)/(i+j-)*dp[i-][j-]);

                     else

                     dp[i][j] = j*1.0/(i+j)*dp[i-][j-];

                 }

                 else

                 {

                     dp[i][j] = i*1.0/(i+j)+j*1.0/(i+j)*dp[i][j-];

                 }

                 //cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;

             }

         printf("%.9lf\n",dp[a][b]);

     }

     return ;

 }

第四题--POJ 2151 Check the difficulty of problems

这个题正推不好推，可以求逆，dp[i][j][g]表示第i个队在前g个题里解决了j道题的概率 再令开一dd[i][j]累加和保存第i队最多解决了j道题的概率

这样依次求出每队解决大于1道题的概率减掉每队解决少于n道的概率 即为每队至少解决一道并且冠军队解决至少n道的概率

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 using namespace std;

 #define N 1010

 #define LL long long

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 double dp[N][][],dd[N][];

 double p[N][];

 int main()

 {

     int i,j,n,m,t,g,e;

     while(cin>>m>>t>>n)

     {

         if(!n||!m||!t) break;

         memset(dp,0.0,sizeof(dp));

         memset(dd,0.0,sizeof(dd));

         for(i = ; i <= t ; i++)

         {

             dp[i][][] = 1.0;

             for(j = ; j <= m ;j++)

             {

                 cin>>p[i][j];

                 dp[i][][j] = (1.0-p[i][j])*dp[i][][j-];

             }

             dd[i][] = dp[i][j][m];

         }

         for(i =  ;i <= t ;i++)

             for(j =  ;j <= m ;j++)

             {

                 e =  ;

                 for(g = j ;g <= m ; g++)

                 {

                     dp[i][j][g] = dp[i][j-][g-]*p[i][g]+dp[i][j][g-]*(-p[i][g]);

                 }

                 dd[i][j] = dd[i][j-]+dp[i][j][m];

             }

         double ans = 1.0,ss=1.0;

         for(i = ; i <= t; i++)

         {

             ans*=dd[i][m]-dd[i][];

             ss*=dd[i][n-]-dd[i][];

         }

         printf("%.3f\n",ans-ss);

     }

     return ;

 }

第五题--POJ 2096 Collecting Bugs （简单期望题）

学习完这题可以了解到这一类期望题的解法，确定好一个边界状态，可能是初态也可能是终态，然后向后或向前推。

这题可以确定的为终态，dp[n][s] = 0. 然后倒推就可以了 dp[i][j] = dp[i][j+1]*(s-j)*1.0/s*i/n+dp[i+1][j]*(n-i)/n*j/s+dp[i+1][j+1]*(n-i)/n*(s-j)/s+1+i*j*1.0/n/s;

一个方程一个未知数，dp[0][0]即为答案。

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 using namespace std;

 #define N 1010

 #define LL long long

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 double dp[N][N];

 int main()

 {

     int n,s,i,j;

     while(cin>>n>>s)

     {

         memset(dp,0.0,sizeof(dp));

         for(i = n ; i >=  ;i--)

             for(j = s ; j >=  ;j--)

             {

                 if(i==n&&j==s) continue;

                 dp[i][j] = dp[i][j+]*(s-j)*1.0/s*i/n+dp[i+][j]*(n-i)/n*j/s+

                 dp[i+][j+]*(n-i)/n*(s-j)/s+;

                 dp[i][j] = dp[i][j]/(-(i*j*1.0/n/s));

             }

         printf("%.4f\n",dp[][]);

     }

     return ;

 }

第六题--HDU 3853 LOOPS（简单期望题）

与上一题类似，可以确定终态 dp[r][c] = 0.然后根据可走的概率进行倒推，注意可能会有无解的情况，p[i][j][0]=1就会进入死循环。

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 using namespace std;

 #define N 1010

 #define LL long long

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 double dp[N][N];

 double p[N][N][];

 int main()

 {

     int i,j,r,c;

     while(cin>>r>>c)

     {

         memset(dp,0.0,sizeof(dp));

         for(i = ; i <= r ; i++)

         {

             for(j = ; j <= c; j++)

             {

                 for(int g =  ; g <  ; g++)

                 scanf("%lf",&p[i][j][g]);

             }

         }

         for(i = r ; i >=  ; i--)

         {

             for(j = c ; j >=  ; j--)

             {

                 if(i==r&&j==c) continue;

                 dp[i][j] = dp[i+][j]*p[i][j][]+dp[i][j+]*p[i][j][]+;

                 if(fabs(-p[i][j][])<eps) continue;

                 dp[i][j] = dp[i][j]/(-p[i][j][]);

             }

         }

         printf("%.3lf\n",dp[][]);

     }

     return ;

 }

第七题--HDU 4405 Aeroplane chess （简单期望题）

投掷骰子的问题，也是一样的问题，确定终态求dp[0]。

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 using namespace std;

 #define N 101000

 #define LL long long

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 int f[N];

 double dp[N];

 int main()

 {

     int n,m,i,j;

     while(cin>>n>>m)

     {

         if(!n&&!m) break;

         memset(f,,sizeof(f));

         memset(dp,,sizeof(dp));

         int x,y;

         for(i =  ;i <=m ; i++ )

         {

             cin>>x>>y;

             f[x] = y;

         }

         for(i = n- ; i >=  ; i--)

         {

             if(f[i])

             dp[i] += dp[f[i]];

             else

             {

                 for(j =  ;j <= ; j++)

                 dp[i] += dp[i+j]*1.0/;

                 dp[i]+=;

             }

         }

         printf("%.4f\n",dp[]);

     }

     return ;

 }

第八题--ZOJ 3640 Help Me Escape （简单期望题）

这个题是d的战斗力值  也就是当战斗力为多少的时候可以确定一个终态 ，很显然当值为maxz+1 的时候 它最大可达2*maxz.

这样就可以写出递推方程 dp[i] = (dp[i+c[j]]+1)*1/n;(第j出口所需战斗力》=i） dp[i] += day[j] (第j出口所需战斗力<i)

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 using namespace std;

 #define N 20010

 #define LL long long

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 int c[];

 double dp[N];

 int main()

 {

     int n,f,i,j;

     while(cin>>n>>f)

     {

         memset(dp,,sizeof(dp));

         for(i = ; i < n ;i++)

         cin>>c[i];

         sort(c,c+n);

         for(i = *c[n-] ; i >= f ; i--)

         {

             int o = ,k=;

             double t = ,tt=;

             for(j =  ; j < n ;j++)

             {

                 if(i>c[j])

                 {

                     int d = (1.0+sqrt(5.0))/*c[j]*c[j];

                     t+=1.0/n*d;

                 }

                 else

                 {

                     k++;

                     if(c[j]==) o++;

                     else

                     t+=1.0/n*(dp[i+c[j]]+);

                 }

             }

             if(o&&fabs(-o*1.0/n)>eps)

             dp[i] += (t+)/(-o*1.0/n);

             dp[i] += t;

         }

         printf("%.3f\n",dp[f]);

     }

     return ;

 }

H第九题--DU 4336 Card Collector(简单期望题）

状压一下，然后确定终态倒推。

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 using namespace std;

 #define N 20010

 #define LL long long

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 double dp[<<],p[];

 int main()

 {

     int n,i,j,g;

     while(scanf("%d",&n)!=EOF)

     {

         memset(dp,,sizeof(dp));

         for(i =  ;i < n; i++)

         scanf("%lf",&p[i]);

         for(j = (<<n)- ; j>= ; j--)

         {

             double t = ;

             double o = ;

             for(g = ; g < n ;g++)

             if((<<g)&j) continue;

             else

             {

                 o+=p[g];

                 t+=p[g]*dp[j+(<<g)];

             }

             if(fabs(o)>eps)

             dp[j] = (t+)/o;

         }

         printf("%f\n",dp[]);

     }

     return ;

 }

第十题--SGU 495 Kids and Prizes（简单期望题）

正推题，这个题比较巧妙，可以确定初始态dp[1] = 1,因为第一个人拿到球的概率就为1，那么第i个拿到球的期望就为，他拿到球的概率*（dp[i-1]+1），他拿到球的概率就等于有球的房间/总房间

那么有球的房间就为n-dp[i-1]，因为期望就为球数，所以dp[i-1]就为拿走的球数。

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 using namespace std;

 #define N 100010

 #define LL long long

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 double dp[N];

 int main()

 {

     int i,n,m;

     while(cin>>n>>m)

     {

         memset(dp,,sizeof(dp));

         dp[] = ;

         for(i = ; i <= m ;i++)

         dp[i] = (dp[i-]+)*(-dp[i-]/n)+dp[i-]*dp[i-]/n;

         printf("%.10f\n",dp[m]);

     }

     return ;

 }

第十一题--ZOJ 3329 One Person Game（简单期望题）

也是比较好推的题目，相对前面来说会多一个未知数，但是推到最后就会发现只有一个未知数，一个方程一个未知数，可以求解。

可以把每一步的期望分为2部分保存，可以准确算出的用dp[i]表示 依旧是未知的用o[i]保存他的系数，留到最后求解。

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 using namespace std;

 #define N 1010

 #define LL long long

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 double dp[N],p[N],o[N];

 int main()

 {

     int i,j,n,k1,k2,k3,g,a,b,c,t;

     cin>>t;

     while(t--)

     {

         memset(dp,,sizeof(dp));

         memset(p,,sizeof(p));

         memset(o,,sizeof(o));

         cin>>n>>k1>>k2>>k3>>a>>b>>c;

         int k = k1+k2+k3;

         for(i = ; i <= k1 ; i++)

             for(j = ;j <= k2 ; j++)

                 for(g = ; g <= k3 ; g++)

                 {

                     if(i==a&&j==b&&g==c) continue;

                     p[i+j+g]+=1.0/(k1*k2*k3);

                 }

         for(i = n ; i >=  ; i--)

         {

             for(j = ; j <= k ; j++)

             {

                 dp[i]+=dp[i+j]*p[j];

                 o[i]+=p[j]*o[i+j];

             }

             dp[i]+=;

             o[i]+=1.0/(k1*k2*k3);

         }

         if(fabs(-o[])>eps)

         dp[] = dp[]/(-o[]);

         printf("%.14f\n",dp[]);

     }

     return ;

 }

第十二题--HDU 4652 Dice

有两种询问，一种一个推法，n个相同的话,dp[i]表示最后有连续i个相同的到最后有n个相同的点数的期望，dp[i] = 0,dp[i] = 1.0/m*dp[i+1]+1+(m-1)/m*dp[1];

另开一数组保存dp[1] 的系数，最后求解。

n个两辆不同，与之类似 dp[i] = ((m-i)*1.0/m*dp[i+1]+1)+1.0/m*dp[1]+1.0/m*dp[2]+....+1.0/m*dp[i]; 化简一下，每次可以消掉一个未知数，求到dp[1]的时候自然只剩了一个未知数。

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 using namespace std;

 #define N 1000010

 #define LL long long

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 double dp[N],o[N];

 int main()

 {

     int i,t,n,m,k;

     while(cin>>t)

     {

         while(t--)

         {

             memset(dp,,sizeof(dp));

             memset(o,,sizeof(o));

             scanf("%d%d%d",&k,&m,&n);

             if(k==)

             {

                 for(i = n- ; i >=  ; i--)

                 {

                     dp[i] = 1.0/m*dp[i+]+;

                     o[i] = 1.0/m*o[i+]+(m-)*1.0/m;

                 }

                 dp[] = dp[]/(-o[]);

                 dp[] = dp[]+;

                 printf("%.12f\n",dp[]);

             }

             else

             {

                 for(i = n- ;i >=  ; i--)

                 {

                     dp[i] = ((m-i)*1.0/m*dp[i+]+)/(-(m-i)*1.0/m*o[i+]-1.0/m);

                     o[i] = ((m-i)*1.0/m*o[i+]+1.0/m)/(-(m-i)*1.0/m*o[i+]-1.0/m);

                 }

                 dp[] = dp[]+;

                 printf("%.12f\n",dp[]);

             }

         }

     }

     return ;

 }

第十三题--HDU 4035 Maze（中等期望题）

树上求期望的题，其实也与之类似，仔细想下会发现叶子节点的期望状态比较好确定，因为它只有一个父亲节点所以这样写出来的方程会只有2个未知数，一个是父亲节点一个是1号节点，到最后父亲节点肯定只有1，所以又会变成一个方程一个未知数。

dp[i]表示第i节点到满足结果的期望。

i为叶子节点 dp[i] = p1i*dp[1]+p2i*dp[fa[i]]+p3i*exit（exit==0)

这样可以多开两个数组存两个未知数的系数。

i为非叶子节点 dp[i] = p1i*dp[1]+p2i*1/k*dp[v](v与i相连的节点，共有K个）+p3i*exit。

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 #include<vector>

 using namespace std;

 #define N 100010

 #define LL long long

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 vector<int>ed[N];

 double dp[N],p[N][];

 double o[N][];

 int flag;

 void dfs(int u,int pre)

 {

     if(!flag) return ;

     int i;

     dp[u] = p[u][];

     o[u][] = p[u][];

     o[u][] = p[u][];

     int k = ed[u].size();

     double pp = ;

     for(i = ; i < k ; i++)

     {

         int v = ed[u][i];

         if(v==pre) continue;

         dfs(v,u);

         dp[u]+=p[u][]/k*dp[v];

         o[u][]+=p[u][]/k*o[v][];

         pp+=p[u][]/k*o[v][];

     }

     if(u==)

     {

         if(fabs(-(o[u][]+pp))>eps)

         dp[u] = dp[u]/(-(o[u][]+pp));

         else

         flag = ;

         return;

     }

     if(fabs(-pp)>eps)

     {

         dp[u] = (dp[u])/(-pp);

         o[u][] = (o[u][])/(-pp);

         o[u][] = p[u][]/k/(-pp);

     }

     else

     {

         flag = ;

         return ;

     }

 }

 int main()

 {

     int i,j,t,n;

     int kk = ;

     cin>>t;

     while(t--)

     {

         memset(dp,,sizeof(dp));

         memset(o,,sizeof(o));

         scanf("%d",&n);

         flag = ;

         for(i =  ;i <= n ;i++)

         ed[i].clear();

         for(i = ; i < n ;i++)

         {

             int u,v;

             scanf("%d%d",&u,&v);

             ed[u].push_back(v);

             ed[v].push_back(u);

         }

         for(i = ; i <=n ;i++)

         {

             int x,y;

             scanf("%d%d",&x,&y);

             p[i][] = x/100.0;

             p[i][] = y/100.0;

             p[i][] = -p[i][]-p[i][];

         }

         dfs(,-);

         printf("Case %d: ",++kk);

         if(flag)

         printf("%f\n",dp[]);

         else

         puts("impossible");

     }

     return ;

第十四题--HDU 4418 Time travel（高斯消元求期望）

这个题意吧有点难理解。。是这个时光机每次可以走1-m步 概率分别为p[i]。

为了好做，可以加n-2个点统一方向， 0 1 2 3 2 1

这样dp[i] = (dp[i+1]+1)*p[i+1]+(dp[i+2]+2)*p[i+2]+...(dp[i+m]+m)*p[i+m];

这样会发现无论你倒推还是正推都无法减少未知数，不过可以列出来n-2个方程，n-2个未知数，高斯消元。

需要先bfs出是否能够达到，然后保留能够达到的点。

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 using namespace std;

 #define N 205

 #define LL long long

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 double p[N],a[N][N],ans[N];

 int n,m,y,x,d,dis[N],g;

 int zn;

 bool vis[N];

 void gauss(int zw,int zr)

 {

     int i,j,k,g = ;

     for(k =  ; k < zw && g < zr; k++,g++)

     {

         i = k;

         for(j = k+ ; j <= zw ; j++)

         {

             if(fabs(a[j][g])>fabs(a[i][g]))

             i = j;

         }

         if(fabs(a[i][g])<eps)

         {

             continue;

         }

         if(i!=k)

         for(j = k ;j <= zr ; j++)

         swap(a[i][j],a[k][j]);

         for(i = k+ ; i <= zw ; i++)

         {

             if(fabs(a[i][k])<eps) continue;

             double s = a[i][g]/a[k][g];

             a[i][g] = 0.0;

             for(j = g+ ; j <= zr; j++)

                 a[i][j] -= s*a[k][j];

         }

     }

     for(i = zw ; i >=  ; i--)

     {

         if(fabs(a[i][i])<eps) continue;

         double s = a[i][zn];

         for(j = i+ ; j <= zw ;j++)

         s-=a[i][j]*ans[j];

         ans[i] = s/a[i][i];

     }

 }

 int bfs()

 {

     int i;

     queue<int>q;

     memset(vis,,sizeof(vis));

     q.push(x);

     vis[x] = ;

     int ff = ;

     while(!q.empty())

     {

         int u = q.front();

         q.pop();

         if(u==y||zn-u==y)

         {

             ff = ;

             continue;

         }

         for(i = ; i <= g; i++)

         {

             int v = (u+dis[i])%zn;

             if(!vis[v])

             {

                 vis[v] = ;

                 q.push(v);

             }

         }

     }

     return ff;

 }

 int main()

 {

     int t,i,j;

     cin>>t;

     while(t--)

     {

         memset(a,,sizeof(a));

         memset(ans,,sizeof(ans));

         scanf("%d%d%d%d%d",&n,&m,&y,&x,&d);

         zn = *n-;

         g = ;

         double sum = ;

         for(i= ; i <= m; i++)

         {

             int  pp;

             scanf("%d",&pp);

             if(pp>)

             {

                 p[++g] = pp/100.0;

                 dis[g] = i;

                 sum+=p[g]*i;

             }

         }

         if(d>)

         x = zn-x;

         if(x==y)

         {

             puts("0.00");

             continue;

         }

         if(!bfs())

         {

             puts("Impossible !");

             continue;

         }

         for(i =  ; i < zn ; i++)

         {

             if(!vis[i]) continue;

             a[i][i] = ;

             if(i==y||y==zn-i) continue;

             for(j =  ; j <= g ;j++)

             {

                 int dd = (dis[j]+i)%zn;

                 a[i][dd]-=p[j];

             }

             a[i][zn] += sum;

         }

         gauss(zn-,zn);

         printf("%.2f\n",ans[x]);

     }

     return ;

 }

第十五题--HDU 4089 Activation(中等概率题）

这个题因为会出现循环求所以有求期望的感觉。

分情况看一下 dp[i][j]表示队里有i个人 他在第j的位置到最终结果的概率。

j==1 dp[i][1] = p1*dp[i][1]+p2*dp[i][i]+p4.

k>=j>1 dp[i][j] = p1*dp[i][j]+p2*dp[i][j-1]+p3*dp[i-1][j-1]+p4;

j>k  dp[i][j] = p1*dp[i][j]+p2*dp[i][j-1]+p3*dp[i-1][j-1];

因为一个i循环里面只有一个dp[i][i]事未知的，可以开一个一维数组保存dp[i][j]里面还有dp[i][i]的系数。

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 using namespace std;

 #define N 2010

 #define LL long long

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 double dp[N][N],o[N];

 int main()

 {

     int i,j,n,m,k;

     double p1,p2,p3,p4;

     while(cin>>n>>m>>k)

     {

         scanf("%lf%lf%lf%lf",&p1,&p2,&p3,&p4);

         memset(dp,,sizeof(dp));

         memset(o,,sizeof(o));

         int flag = ;

         if(fabs(-p2-p1)<eps)

         flag = ;

         else

         dp[][] = p4/(-p2-p1);

         for(i =  ;i <= n ;i++)

         {

             o[] = ;

             for(j =  ; j <= i; j++)

             {

                 if(j<=k)

                 {

                     if(j==)

                     {

                         dp[i][j]+=p4;

                         o[j] = p2;

                     }

                     else

                     {

                         dp[i][j] += p4+p2*dp[i][j-]+p3*dp[i-][j-];

                         o[j] = p2*o[j-];

                     }

                 }

                 else

                 {

                    dp[i][j]+= p2*dp[i][j-]+p3*dp[i-][j-];

                    o[j] = p2*o[j-];

                 }

                 if(j==i)

                 {

                     if(fabs(-p1-o[j])<eps)

                     {

                         flag = ;

                         break;

                     }

                     dp[i][j] = dp[i][j]/(-p1-o[j]);

                 }

                 else

                 {

                     if(fabs(-p1-o[j])<eps)

                     {

                         flag = ;

                         break;

                     }

                     dp[i][j] = dp[i][j]/(-p1);

                     o[j] = o[j]/(-p1);

                 }

             }

             if(!flag) break;

             for(j = ;j < i ;j++)

             dp[i][j]+=dp[i][i]*o[j];

         }

         if(flag)

         printf("%.5f\n",dp[n][m]);

         else

         printf("%.5f\n",0.0);

     }

     return ;

 }

第十六题--ZOJ 3380 Patchouli's Spell Cards（中等题）

这题没有推出来。。。 组合题，

dp[i,j]  表示用前i个数字在m个里放了j个位置，这些数字不一定都有用到
概率dp专场   dp[i,j] = ∑ dp[i-1,j-k]*C[m-(j-k),k]          0≤k≤j , k<l
概率dp专场   最后答案为dp[n,m]

个人认为做法很棒。。

题解参照

 import java.text.*;

 import java.io.*;

 import java.util.*;

 import java.math.*;

 import java.applet.*;

 public class Main

 {

     public static void main(String[] args)

     {

         Scanner  cin = new Scanner(System.in);

         BigInteger [][]dp = new BigInteger[][];

         BigInteger o = BigInteger.valueOf();

         BigInteger [][]c = new BigInteger[][];

         int n,m,i,j,l,k;

         for(i=;i<;i++)c[i][]=c[i][i]=BigInteger.valueOf();

             for(i=;i<;i++){

                     for(j=;j<i;j++)

                         c[i][j]=c[i-][j-].add(c[i-][j]);

                 }

         while(cin.hasNext())

         {

             m = cin.nextInt();

             n = cin.nextInt();

             l = cin.nextInt();

             BigInteger s1 ,s2 = BigInteger.valueOf();

             s1 = BigInteger.valueOf(n);

             s1 = s1.pow(m);

             if(l>m)

             {

                 System.out.println("mukyu~");

                 continue;

             }

             else if(l>m/)

             {

                 for(i=l;i<=m;i++)

                 {

                     s2=s2.add(c[m][i].multiply( BigInteger.valueOf(n-).pow(m-i) ));

                 }

                 s2=s2.multiply(BigInteger.valueOf(n));

             }

             else

             {

                 for(i = ; i <= n ;i++)

                     for(j = ; j <= m; j++)

                             dp[i][j] = o;

                 dp[][] = BigInteger.ONE;

                 for(i = ; i <= n ;i++)

                 {

                     for(j = ; j <= m ;j++)

                     {

                         for(k = ; k <= Math.min(j, l-) ;k++)

                         dp[i][j] = dp[i][j].add(dp[i-][j-k].multiply(c[m-(j-k)][k]));

                     }

                 }

                 s2 = dp[n][m];

                 s2 = s1.subtract(s2);

             }

             BigInteger gc = s2.gcd(s1);

             System.out.println(s2.divide(gc)+"/"+s1.divide(gc));

         }

     }

 }
上一篇：.NET轻量级MVC框架：Nancy入门教程(二)——Nancy和MVC的简单对比


下一篇：RobotFrameWork接口设计规范