程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 2537 Tight words 概率dp

poj 2537 Tight words 概率dp

編輯:C++入門知識

poj 2537 Tight words 概率dp


分析:

用計數dp思想:DP[I][J]=(DP[I-1][J-1]+DP[I-1][J]+DP[I-1][J+1]),最後再除pow(k+1,n)容易爆精度,改用概率dp思想DP[I][J]=(DP[I-1][J-1]+DP[I-1][J]+DP[I-1][J+1])/(k+1)即可。

代碼:

 

//poj 2537
//sep9
#include
using namespace std;
double dp[128][16];

int main()
{
	int k,n;
	while(scanf("%d%d",&k,&n)==2){
		for(int i=0;i<=n;++i)
			for(int j=0;j<=k;++j)
				dp[i][j]=0;
		for(int i=0;i<=k;++i)
			dp[1][i]=1.0/(k+1);
		for(int i=2;i<=n;++i){
			for(int j=0;j<=k;++j)
				dp[i][j]=dp[i-1][j]/(k+1);
			for(int j=1;j<=k;++j)
				dp[i][j]+=dp[i-1][j-1]/(k+1);
			for(int j=0;j

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved