POJ 1189釘と小球[dp]

考え方:
簡単なdpは、確率の計算過程を手動でシミュレートすると、どのようにするかがわかります.

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define llong long long int
using namespace std;
const int N=105;
const int inf=(1<<30);
int n,m;
char a[N][N];
llong d[N][N];
llong gcd(llong a,llong b)
{
	return (b>0)?gcd(b,a%b):a;
}
void solve()
{
	memset(d,0,sizeof(d));
	llong sum=1;
	sum<<=n;
	d[1][1]=sum;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=2*i-1;j++)
		{
			if(j%2)
			{
				int k=(j+1)/2;
				if(a[i][k]=='*')
				{
					d[i+1][j]+=d[i][j]/2;
					d[i+1][j+2]+=d[i][j]/2;
				}
				else
				{
					d[i+1][j+1]+=d[i][j];
				}
			}
			else
			{
				d[i+1][j+1]+=d[i][j];
			}
		}
	}
	n++;
	llong r=gcd(sum,d[n][2*m+1]);
	printf("%lld/%lld
",d[n][2*m+1]/r,sum/r);
}
int main()
{
	scanf("%d%d",&n,&m);
	char tmp;
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=i;)
	  {
		  scanf("%c",&tmp);
		  if(tmp=='*'||tmp=='.')
		  {
			  a[i][j]=tmp;
			  j++;
		  }
	  }
	solve();
	return 0;
}