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

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 register

inline void Rin(RG int &x) {

  x=;RG int c=getchar(),f=;

  for(;c<||c>;c=getchar())

    if(!(c^))f=-;

  for(;c>&&c<;c=getchar())

    x=(x<<)+(x<<)+c-;

  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/);

  putchar(x%+); }

L gcd(RG L a,RG L b) {

  return b?gcd(b,a%b):a; }

bool _map[][];

int n,m;

struct fr{

  L n,d;

  fr(RG L _=,RG L __=) : n(_),d(__) {} }f[][];

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=; i<=n; i++)

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

      ploy(_map[i][j]);

  f[][]=fr(,);

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

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

      rec(f[i][j]),

      _map[i][j]?

    f[i+][j]+=f[i][j]*fr(,),f[i+][j+]+=f[i][j]*fr(,):

    f[i+][j+]+=f[i][j];

  rec(f[n+][m+]);

  Shiki(f[n+][m+].n); putchar('/'); Shiki(f[n+][m+].d);

  return ;

}