POJ 1189 记忆化搜索

钉子和小球

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 7218		Accepted: 2164

Description

有一个三角形木板,竖直立放，上面钉着n(n+1)/2颗钉子，还有(n+1)个格子（当n=5时如图1）。每颗钉子和周围的钉子的距离都等于d，每个格子的宽度也都等于d，且除了最左端和最右端的格子外每个格子都正对着最下面一排钉子的间隙。
让一个直径略小于d的小球中心正对着最上面的钉子在板上自由滚落，小球每碰到一个钉子都可能落向左边或右边（概率各1/2），且球的中心还会正对着下一颗将要碰上的钉子。例如图2就是小球一条可能的路径。
我们知道小球落在第i个格子中的概率pi=pi=，其中i为格子的编号，从左至右依次为0,1,...,n。
现在的问题是计算拔掉某些钉子后，小球落在编号为m的格子中的概率pm。假定最下面一排钉子不会被拔掉。例如图3是某些钉子被拔掉后小球一条可能的路径。

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

Source

Noi 99

状态转移方程：

if(tar[i][j]=='*'){

ans[i+1][j]=ans[i+1][j]+(ans[i][j]>>1);

ans[i+1][j+1]=ans[i+1][j+1]+(ans[i][j]>>1);

}

else{

ans[i+2][j+1]=ans[i+2][j+1]+ans[i][j];

}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define LL long long
using namespace std;

const int inf=0x3fffffff;
const int maxn=57;
char tar[maxn][maxn];
long long fm,fz,ubt,ans[maxn][maxn];
int n,m;

long long gcd(long long a,long long b)
 {
     return b==0?a:gcd(b,a%b);
}

int main()
{
    //freopen("in.txt","r",stdin);
    char c[5];
    while(~scanf("%d%d",&n,&m)){
        memset(tar,0,sizeof(tar));
        memset(ans,0,sizeof(ans));
        for(int i=1;i<=n;i++)
            for(int j=1;j<=i;j++)
        {
            scanf("%s",c);
            tar[i][j]=c[0];
        }
        ans[1][1]=1LL<<n;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=i;j++)
        {
            if(tar[i][j]=='*'){
                ans[i+1][j]=ans[i+1][j]+(ans[i][j]>>1);
                ans[i+1][j+1]=ans[i+1][j+1]+(ans[i][j]>>1);
            }
            else{
                ans[i+2][j+1]=ans[i+2][j+1]+ans[i][j];
            }
        }
    long long ans1=ans[n+1][m+1];
    long long  sum=0;
     for(int i=1;i<=n+1;i++)
     {
         sum+=ans[n+1][i];
     }
     long long  k;
     k=gcd(sum,ans1);
     printf("%lld/%lld\n",ans1/k,sum/k);
    }
    return 0;
}