zoj 1883 - Tight Words
來源：程序員人生 發布時間：2014-09-29 23:11:24 閱讀次數：3761次
題目：如果一個單詞的每個字母都不相差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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
