概率+DP,比较经典的题。按照递推的方式计算概率。


#include <cstdio>
#include 
<cstring>
int n,m,i,j,a[100][100];
long long p[100][100][2];
inline 
long long gcd(long long a,long long b) {
    
if (b==0return a;
    
else return gcd(b,a%b);
}

inline 
void add(long long a,long long b,long long &c,long long &d) {
    
long long t1,t2,t3,t4;
    t1
=gcd(b,d);
    t2
=b/t1*d;
    t3
=d/t1*a;
    t4
=b/t1*c;
    c
=t3+t4;
    d
=t2;
    t1
=gcd(c,d);
    c
/=t1;
    d
/=t1;
}
;
int main () {
    scanf(
"%d%d",&n,&m);
    
for (i=1;i<=n;i++for (j=1;j<=i;j++{
        
char s[100];
        scanf(
"%s",s);
        
if (s[0]=='*') a[i][j]=1else a[i][j]=0;
    }

    memset(p,
0,sizeof(p));
    
for (i=1;i<=n+1;i++for (j=1;j<=i;j++{
        p[i][j][
0]=0;
        p[i][j][
1]=1;
    }

    p[
1][1][0]=p[1][1][1]=1;
    
for (i=1;i<=n;i++for (j=1;j<=i;j++{
        
if (a[i][j]==1{
            add(p[i][j][
0],2*p[i][j][1],p[i+1][j][0],p[i+1][j][1]);
            add(p[i][j][
0],2*p[i][j][1],p[i+1][j+1][0],p[i+1][j+1][1]);
        }

        
else add(p[i][j][0],p[i][j][1],p[i+2][j+1][0],p[i+2][j+1][1]);
    }

    printf(
"%I64d/%I64d\n",p[n+1][m+1][0],p[n+1][m+1][1]);
    
return 0;
}
posted on 2007-10-04 20:47 Felicia 阅读(773) 评论(4)  编辑 收藏 引用 所属分类: 动态规划
Comments

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理