釘子和小球

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];

}

?

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<algorithm>
 6 #define LL long long
 7 using namespace std;
 8 
 9 const int inf=0x3fffffff;
10 const int maxn=57;
11 char tar[maxn][maxn];
12 long long fm,fz,ubt,ans[maxn][maxn];
13 int n,m;
14 
15 long long gcd(long long a,long long b)
16  {
17      return b==0?a:gcd(b,a%b);
18 }
19 
20 int main()
21 {
22     //freopen("in.txt","r",stdin);
23     char c[5];
24     while(~scanf("%d%d",&n,&m)){
25         memset(tar,0,sizeof(tar));
26         memset(ans,0,sizeof(ans));
27         for(int i=1;i<=n;i++)
28             for(int j=1;j<=i;j++)
29         {
30             scanf("%s",c);
31             tar[i][j]=c[0];
32         }
33         ans[1][1]=1LL<<n;
34         for(int i=1;i<=n;i++)
35             for(int j=1;j<=i;j++)
36         {
37             if(tar[i][j]=='*'){
38                 ans[i+1][j]=ans[i+1][j]+(ans[i][j]>>1);
39                 ans[i+1][j+1]=ans[i+1][j+1]+(ans[i][j]>>1);
40             }
41             else{
42                 ans[i+2][j+1]=ans[i+2][j+1]+ans[i][j];
43             }
44         }
45     long long ans1=ans[n+1][m+1];
46     long long  sum=0;
47      for(int i=1;i<=n+1;i++)
48      {
49          sum+=ans[n+1][i];
50      }
51      long long  k;
52      k=gcd(sum,ans1);
53      printf("%lld/%lld\n",ans1/k,sum/k);
54     }
55     return 0;
56 }

?

?

?

轉載于:https://www.cnblogs.com/codeyuan/p/4274727.html

總結

以上是生活随笔為你收集整理的POJ 1189 记忆化搜索的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。