UVA_10081

    我们可以用f[i][j]表示第i个字符为j时的tight words的比率，那么有f[i][j]=1.0/(K+1)*(f[i-1][j-1]+f[i-1][j]+f[i-1][j+1])，当然括号里面的三项不一定都存在，分情况讨论一下即可。

#include
     
       #include
      
        #define MAXK 15 #define MAXN 110 int N, K; double f[MAXN][MAXK]; void solve() {
   int i, j; double res = 0; for(i = 0; i <= K; i ++)         f[1][i] = 100.0 / (K + 1); for(i = 2; i <= N; i ++)     {
           f[i][0] = 1.0 / (K + 1) * (f[i - 1][0] + f[i - 1][1]); for(j = 1; j < K; j ++)             f[i][j] = 1.0 / (K + 1) * (f[i - 1][j - 1] + f[i - 1][j] + f[i - 1][j + 1]);         f[i][K] = 1.0 / (K + 1) * (f[i - 1][K - 1] + f[i - 1][K]);     } for(i = 0; i <= K; i ++)         res += f[N][i];     printf("%.5lf\n", res); } int main() {
   while(scanf("%d%d", &K, &N) == 2)     {
   if(K <= 1)             printf("100.00000\n"); else             solve();     } return 0; }