期望DP

2022-09-23 13:08:17

BZOJ 1415

 #include <iostream>

 #include <cstring>

 #include <algorithm>

 #include <cstdio>

 using namespace std;

 const int Maxn=;

 int t[Maxn],n,m,S,T,now,p[Maxn][Maxn],head[Maxn],dis[Maxn],u,v,cnt;

 double f[Maxn][Maxn];

 struct EDGE

 {

     int to,next;

 }edge[Maxn<<];

 inline void Add(int u,int v)

 {edge[cnt].to=v;edge[cnt].next=head[u];head[u]=cnt++;}

 void Dfs(int u,int top)

 {

     for (int i=head[u];i!=-;i=edge[i].next)

         if (dis[edge[i].to]==- || dis[edge[i].to]>dis[u]+ || (dis[edge[i].to]==dis[u]+ && p[now][edge[i].to]>top))

         {

             dis[edge[i].to]=dis[u]+;

             p[now][edge[i].to]=top;

             Dfs(edge[i].to,top);

         }

 }

 double F(int S,int T)

 {

     if (f[S][T]!=) return f[S][T];

     if (S==T) return ;

     if (p[p[S][T]][T]==T || p[S][T]==T) return ;

     double res=;

     for (int i=head[T];i!=-;i=edge[i].next)

         res+=F(p[p[S][T]][T],edge[i].to);

     res+=F(p[p[S][T]][T],T);

     res/=(double)(t[T]+1.0);

     res+=;

     return f[S][T]=res;

 }

 int main()

 {

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

     scanf("%d%d",&S,&T);

     memset(head,-,sizeof(head));

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

     {

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

         Add(u,v),Add(v,u);

         t[u]++; t[v]++;

     }

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

     {

         memset(dis,-,sizeof(dis));

         dis[i]=;

         for (int j=head[i];j!=-;j=edge[j].next)

         {

             now=i;

             dis[edge[j].to]=;

             Dfs(edge[j].to,edge[j].to);

         }

         for (int j=head[i];j!=-;j=edge[j].next) p[i][edge[j].to]=edge[j].to;

     }

     printf("%.3lf\n",F(S,T));

     return ;

 }

C++

BZOJ 1419

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <algorithm>

 using namespace std;

 const int Maxn=;

 double f[][Maxn];

 int R,B,cur;

 inline double Max(double x,double y) {return x>y?x:y;}

 int main()

 {

     scanf("%d%d",&R,&B);

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

     {

         cur^=;

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

         {

             if (i==) {f[cur][j]=; continue;}

             if (j==) {f[cur][j]=f[cur^][j]+;continue;}

             f[cur][j]=Max(,(f[cur^][j]+1.0)*((double)(i)/(double)(i+j))+(f[cur][j-]-1.0)*((double)(j)/(double)(i+j)));

         }

     }

     printf("%.6lf\n",f[cur][B]-5e-);

     return ;

 }

C++

算法合集之《浅析竞赛中一类数学期望问题的解决方法》中有对题目的讲解。

HDU 4405 期望貌似是倒着推的，F[i]=∑F[i+k](k=1~6) /6+1; 但因为又加了一步所以要加一。可以直接跳到的则期望是一样的。

 #include <cstdio>

 #include <cstring>

 const int Maxn=;

 int vis[Maxn],n,m,u,v;

 double F[Maxn];

 int main()

 {

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

     {

         if (n== && m==) break;

         memset(vis,-,sizeof(vis));

         for (int i=;i<=m;i++) scanf("%d%d",&u,&v),vis[u]=v;

         memset(F,,sizeof(F));

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

             if (vis[i]==-)

             {

                 for (int j=;j<=;j++) F[i]+=F[i+j]/6.0;

                 F[i]=F[i]+;

             } else

                 F[i]=F[vis[i]];

         printf("%.4lf\n",F[]);

     }

     return ;

 }

C++

HDU 4089 至今还不是很清楚怎么退的。。

 #include <cstdio>

 const int Maxn=;

 const double eps=1e-;

 double F[Maxn][Maxn],p1,p2,p3,p4,x[Maxn],z[Maxn];

 int n,m,k;

 int main()

 {

     while (scanf("%d%d%d%lf%lf%lf%lf",&n,&m,&k,&p1,&p2,&p3,&p4)!=EOF)

     {

         if (p4<eps)    {puts("0.00000");continue;}

         double p21=p2/(-p1),p31=p3/(-p1),p41=p4/(-p1);

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

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

         {

             x[]=p21; z[]=p41;

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

             {

                 x[j]=x[j-]*p21;

                 z[j]=p31*F[i-][j-]+p21*z[j-];

                 if (j<=k) z[j]+=p41;

             }

             F[i][i]=z[i]/(-x[i]);

             for (int j=;j<i;j++) F[i][j]=x[j]*F[i][i]+z[j];

         }

         printf("%.5lf\n",F[n][m]);

     }

     return ;

 }

C++

POJ 2096 一直末状态推终状态。

 #include<cstdio>

 const int Maxn=;

 double F[Maxn][Maxn];

 int n,s;

 int main()

 {

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

     {

         F[n][s]=;

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

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

             {

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

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

             }

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

     }

     return ;

 }

C++

POJ 3744 矩阵乘法加速线性表达式递推。

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int Maxn=;

 struct Matrix {double a[][]; int x,y;};

 int n,a[Maxn];

 double p,Ans;

 inline Matrix operator * (Matrix A,Matrix B)

 {

     Matrix C; C.x=A.x,C.y=B.y;

     memset(C.a,,sizeof(C.a));

     for (int i=;i<=A.x;i++)

         for (int j=;j<=A.y;j++)

             for (int k=;k<=B.y;k++)

                 C.a[i][j]+=A.a[i][k]*B.a[k][j];

     return C;

 }

 inline Matrix Pow(Matrix x,int y)

 {

     Matrix Ret; Ret.x=,Ret.y=;

     memset(Ret.a,,sizeof(Ret.a));

     Ret.a[][]=Ret.a[][]=;

     while (true)

     {

         if (y&) Ret=Ret*x;

         x=x*x; y>>=;

         if (y==) break;

     }

     return Ret;

 }

 double Get(int t)

 {

     if (t<=) return ;

     if (t==) return ;

     if (t==) return p;

     t-=;

     Matrix M;

     M.x=M.y=;

     M.a[][]=p;

     M.a[][]=-p;

     M.a[][]=;

     M.a[][]=;

     M=Pow(M,t);

     return M.a[][]*p+M.a[][];

 }

 int main()

 {

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

     {

         for (int i=;i<=n;i++) scanf("%d",&a[i]);

         sort(a+,a+n+);

         Ans=;

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

             Ans=Ans*Get(a[i]-a[i-])*(1.0-p);

         printf("%.7lf\n",Ans);

     }

     return ;

 }

C++

POJ 3071 直接DP即可

 #include <cstdio>

 #include <cstring>

 double F[][],p[][];

 int n,Ans;

 int main()

 {

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

     {

         if (n==-) break;

         memset(F,,sizeof(F));

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

             for (int j=;j<=(<<n);j++) scanf("%lf",&p[i][j]);

         for (int i=;i<=(<<n);i++) F[][i]=1.0;

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

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

                 for (int k=;k<=(<<n);k++)

                     if (((j-)>>(i-)^)==((k-)>>i-))

                         F[i][j]+=F[i-][j]*F[i-][k]*p[j][k];

         double Ret=;

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

             if (F[n][i]>Ret) Ans=i,Ret=F[n][i];

         printf("%d\n",Ans);

     }

     return ;

 }

C++

码农公寓

相关文章