首页 > 代码库 > [bzoj1867][Noi1999][钉子和小球] (动态规划)

[bzoj1867][Noi1999][钉子和小球] (动态规划)

2024-09-01 17:10:12   219人阅读

Description

技术分享

Input

第1行为整数n（2<=n<=50）和m（0<=m<=n）。以下n行依次为木板上从上至下n行钉子的信息，每行中‘*’表示钉子还在，‘.’表示钉子被拔去，注意在这n行中空格符可能出现在任何位置。

Output

仅一行，是一个既约分数(0写成0/1)，为小球落在编号为m的格子中的概pm。既约分数的定义：A/B是既约分数，当且仅当A、B为正整数且A和B没有大于1的公因子。

Sample Input

5 2
技术分享





Sample Output

7/16
 

Solution

设f[i][j]代表小球落到位置为(i,j)的概率，分数求解即可

#include <stdio.h>#define L long long#define RG registerinline void Rin(RG int &x) {  x=0;RG int c=getchar(),f=1;  for(;c<48||c>57;c=getchar())    if(!(c^45))f=-1;  for(;c>47&&c<58;c=getchar())    x=(x<<1)+(x<<3)+c-48;  x*=f; }inline void ploy(RG bool &x) {  RG char c=getchar();  while(c!=‘*‘&&c!=‘.‘)c=getchar();  x=c==‘*‘?true:false; }void Shiki(RG L x) {  if(!x)return;  Shiki(x/10);  putchar(x%10+48); }L gcd(RG L a,RG L b) {  return b?gcd(b,a%b):a; }bool _map[55][55];int n,m;struct fr{  L n,d;  fr(RG L _=0,RG L __=1) : n(_),d(__) {} }f[55][55];inline void rec(fr &_this) {  L t=gcd(_this.n,_this.d);  _this.n/=t;  _this.d/=t; }fr operator + (const fr &a,const fr &b) {  fr res;  L t=gcd(a.d,b.d);  res.n=b.d/t*a.n+a.d/t*b.n;  res.d=a.d/t*b.d;  return res; }fr operator * (const fr &a,const fr &b) {  fr res(a.n*b.n,a.d*b.d);  rec(res);  return res; }void operator += (fr &a,const fr &b) {  a=a+b; }int main() {  Rin(n),Rin(m);  for(RG int i=1; i<=n; i++)    for(RG int j=1; j<=i; j++)      ploy(_map[i][j]);  f[1][1]=fr(1,1);  for(RG int i=1; i<=n; i++)    for(RG int j=1; j<=i; j++)      rec(f[i][j]),      _map[i][j]?    f[i+1][j]+=f[i][j]*fr(1,2),f[i+1][j+1]+=f[i][j]*fr(1,2):    f[i+2][j+1]+=f[i][j];  rec(f[n+1][m+1]);  Shiki(f[n+1][m+1].n); putchar(‘/‘); Shiki(f[n+1][m+1].d);  return 0;}

 

[bzoj1867][Noi1999][钉子和小球] (动态规划)


联系
我们