PKU 2537 Tight words
http://poj.org/problem?id=2537
0〜kまでの数字を使って長さnの文字列を作る。
この時、どの隣り合う数字の差も1以内になるような確率を求めろというような問題。
確率dp。
最初個数を数える方針でやろうとして、桁が足りなすぎると考えこんでました。
本格的に解ける問題が見つからなくなりつつある気がします。
long double dp[10][100]; main(){ int n,k; while(cin>>k>>n){ if(!n)break; rep(i,k+1)dp[i][0]=1./(k+1); for(int i=1;i<n;++i){ rep(j,k+1){ dp[j][i]=0; if(j-1>=0)dp[j][i]+=dp[j-1][i-1]/(k+1); dp[j][i]+=dp[j][i-1]/(k+1); if(j+1<=k)dp[j][i]+=dp[j+1][i-1]/(k+1); } } double ans=0; rep(i,k+1)ans+=dp[i][n-1]; printf("%.5f\n",ans*100); } }