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);
  }
}