程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> poj 3744 Scout YYF I 概率dp+矩陣乘法

poj 3744 Scout YYF I 概率dp+矩陣乘法

編輯:關於C++

分析:

dis(k,v1,v2)函數求到當前位置概率為v1,到當前位置之前一步的概率為v2,前進k步到達位置的概率,然後矩陣加速。

代碼:

 

//poj 3744
//sep9
#include 
#include 
using namespace std;
int pos[12];
double p,mat[4][4];
double ans[4][4];

void mul1()
{
	double c[4][4];
	c[0][1]=c[1][0]=c[0][0]=c[1][1]=0.0;
	for(int i=0;i<2;++i)
		for(int j=0;j<2;++j)
			for(int k=0;k<2;++k)
				c[i][j]+=ans[i][k]*mat[k][j];
	for(int i=0;i<2;++i)
		for(int j=0;j<2;++j)
			ans[i][j]=c[i][j];
}

void mul2()
{
	double c[4][4];
	c[0][1]=c[1][0]=c[0][0]=c[1][1]=0.0;
	for(int i=0;i<2;++i)
		for(int j=0;j<2;++j)
			for(int k=0;k<2;++k)
				c[i][j]+=mat[i][k]*mat[k][j];
	for(int i=0;i<2;++i)
		for(int j=0;j<2;++j)
			mat[i][j]=c[i][j];
}

double dis(int len,double val,double val1)
{
	mat[1][0]=1.0;
	mat[0][1]=1-p;
	mat[0][0]=p;
	mat[1][1]=0;
	ans[1][0]=ans[0][1]=0;
	ans[0][0]=ans[1][1]=1.0;
	while(len){
		if(len&1) mul1();
		mul2();
		len>>=1;
	}		
	return ans[0][0]*val+ans[0][1]*val1;
}

int main()
{
	int n;
	while(scanf("%d%lf",&n,&p)==2){
		pos[0]=0;
		for(int i=1;i<=n;++i)
			scanf("%d",&pos[i]);		
		sort(pos+1,pos+1+n);
		double ans=1,a1=1,a0=0;
		for(int i=1;i<=n;++i){
			if(pos[i]==pos[i-1]) continue;
			ans=ans-dis(pos[i]-pos[i-1]-1,a1,0);
			a1=ans;
		}
		printf("%.7lf\n",ans);
	}
	return 0;	
} 


 

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