首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。