http://poj.org/problem?id=1189

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

對于每個沒有挖掉的釘子(i,j)：dp[i+1][j]+=dp[i][j]/2; dp[i+1][j+1]+=dp[i][j]/2; 對于挖掉的釘子(i,j)：dp[i+2][j+1]+=dp[i][j]; */ #include <stdio.h> #include <string.h> #include <algorithm> #include <iostream> using namespace std; typedef long long LL; bool a[2555]; int n,m; LL dp[55][55]; LL gcd(LL x,LL y) { if(y==0)return x; return gcd(y,x%y); } int main() { while(~scanf("%d%d",&n,&m)) { int k=1; for(int i=1; i<=n; i++) { for(int j=1; j<=i; j++) { char str[12]; scanf("%s",str); if(str[0]=='*') { a[k++]=true; } else { a[k++]=false; } //printf("%d\n",a[k-1]); } //puts(""); } memset(dp,0,sizeof(dp)); dp[1][1]=1LL<<n; for(int i=1; i<=n; i++) { int x=i*(i-1)/2; for(int j=1; j<=i; j++) { if(a[j+x]) { dp[i+1][j]+=dp[i][j]/2; dp[i+1][j+1]+=dp[i][j]/2; } else { dp[i+2][j+1]+=dp[i][j]; } } } LL x=1LL<<n; LL y=dp[n+1][m+1]; LL g=gcd(x,y); printf("%lld/%lld\n",y/g,x/g); } return 0; }

本文轉自mfrbuaa博客園博客，原文鏈接：http://www.cnblogs.com/mfrbuaa/p/5137832.html，如需轉載請自行聯系原作者

總結

以上是生活随笔為你收集整理的poj1189 简单dp的全部內容，希望文章能夠幫你解決所遇到的問題。

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