zoj 1883 - Tight Words
来源：程序员人生 发布时间：2014-09-29 23:11:24 阅读次数：3624次
题目：如果一个单词的每个字母都不相差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
",sum*100);
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
