bzoj千题计划189：bzoj1867: [Noi1999]钉子和小球

http://www.lydsy.com/JudgeOnline/problem.php?id=1867

dp[i][j] 落到（i，j）的方案数

dp[i][j]=0.5*dp[i-1][j]   [(i-1,j)位置有钉子] + 0.5*dp[i-1][j-1]    [（i-1.j-1）位置有钉子] + dp[i-1][j-2]    [（i-1，j-2）位置没有钉子]

#include<cstdio>

#include<iostream>

using namespace std;

typedef long long LL;

#define N 52

bool nail[N][N];

LL getgcd(LL a,LL b) { return !b ? a : getgcd(b,a%b); }

struct Fraction

{

    LL molecule,denominator;

    void operator = (int p)

    {

        molecule=p;

        denominator=;

    }

    Fraction operator * (Fraction p)

    {

        Fraction c;

        c.molecule=molecule;

        c.denominator=denominator<<;

        LL gcd=getgcd(c.molecule,c.denominator);

        c.molecule/=gcd;

        c.denominator/=gcd;

        return c;

    }

    void operator += (Fraction p)

    {

        if(!denominator)

        {

            *this=p;

            return;

        }

        Fraction c;

        LL gcd=getgcd(denominator,p.denominator);

        c.denominator=denominator/gcd*p.denominator;

        c.molecule=c.denominator/denominator*molecule+c.denominator/p.denominator*p.molecule;

        *this=c;

    }

    bool have()

    {

        return denominator;

    }

    void print()

    {

        if(!molecule) denominator=;

        cout<<molecule<<'/'<<denominator;

    }

}half;

Fraction dp[N][N];

char getc()

{

    char c;

    while()

    {

        c=getchar();

        if(c=='*'||c=='.') return c;

    }

}

int main()

{

    int n,m;

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

    char c;

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

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

        {

            c=getc();

            if(c=='*') nail[i][j]=true;

        }

    dp[][]=;

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

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

        {

            if(nail[i-][j-] && dp[i-][j-].have()) dp[i][j]+=dp[i-][j-]*half;

            if(nail[i-][j] && dp[i-][j].have()) dp[i][j]+=dp[i-][j]*half;

            if(!nail[i-][j-] && dp[i-][j-].have()) dp[i][j]+=dp[i-][j-];

        }

    dp[n+][m+].print();

}

1867: [Noi1999]钉子和小球

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 880  Solved: 355
[Submit][Status][Discuss]

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