首页 > 代码库 > zoj 1883 - Tight Words

zoj 1883 - Tight Words

题目:如果一个单词的每个字母都不相差1,我们称为紧密的,给你字母集合{0~k},

             问长度为n的单词是紧密的概率。

分析:概率dp。以长度为阶段,结束位置的字符的概率为状态 dp。

             状态:设f(i,j)为长度为i的单词,取自集合{ 0,..,k }的紧密概率;

             转移:f(i,j)= (f(i-1,j-1)+ f(i,j)+ f(i,j+1))/(k+1);

说明:(2011-11-01 17:40)。

#include <iostream>
#include <cstdlib>
#include <stdio.h>

usingnamespace std;

double F[ 101 ][ 10 ];

int main()
{
    int k,n; 
    while ( cin >> k >> n ) {
        double r = 1.0/(1+k);
        for ( int i = 0 ; i <= k ; ++ i )
            F[ 1 ][ i ] = r;
        for ( int i = 2 ; i <= n ; ++ i )
        for ( int j = 0 ; j <= k ; ++ j ) {
            F[ i ][ j ] = F[ i-1 ][ j ]*r;
            if ( j > 0 ) F[ i ][ j ] += F[ i-1 ][ j-1 ]*r;
            if ( j < k ) F[ i ][ j ] += F[ i-1 ][ j+1 ]*r;
        }
        double sum = 0.0;
        for ( int i = 0 ; i <= k ; ++ i )
            sum += F[ n ][ i ];
        printf("%.5lf\n",sum*100);
    }
    return 0;
}

zoj 1883 - Tight Words