POJ 1189-钉子和小球（DP）

第i层有2*i+1种可能的位置（从第1个空位到最后一个空位总共i+1个和i个钉子位置），用d[i][j]表示第i行在第j个位置掉落的概率的分子（分母是2^i）。

如果位置是空位，那么有3种情况：

(1).从上一个同样的位置掉落下来，

(2).掉落到左边的钉子（如果有）并向右走，

(3).掉落到右边的钉子（如果有）并向左走。

如果位置是有钉子的，有2种情况：

(1).这个位置有钉子，那么不可能以这个位置掉落，

(2).这个位置没有钉子，可以从上一个同样的位置掉落下来。

#include
  
   
#include
   
     #include
    
      typedef long long LL; int a[110][110]; LL d[110][210]; char e[1100]; int main(void) { int i,j,n,m,top,lo; LL p,q,sump; scanf("%d%d",&n,&m); while(getchar()==' '){;} for(i=1;i<=n;i++) { gets(e); lo=strlen(e); top=0; for(j=0;j