[动态规划] pku1189 概率
评论22次阅读2007.10.04 20:47; 作者：Felicia
概率+DP，比较经典的题。按照递推的方式计算概率。
下面是我的代码
下载: pku1189.cpp
#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==0) return 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]=1; else 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;
}
#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==0) return 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]=1; else 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;
}
发表回复
- 评论 (0)
- 引用通告 (0)
发表评论 引用通告暂无评论.
暂无引用通告