CF235 Let's Play Osu![dp+概率]

CF235 Let's Play Osu![dp+概率]

題意：

給n個位置，給出1-n上每個位置出現O的概率pi，記分規則如下，連續的x個O記為x^2分，求和，如 XXOOOXOXOOXX得分為

求得分的期望

<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+y7y/vNK7z8KjrM7Sw8fE3LHIvc/I3dLXtdi1w7P2T6Oobl4yo6m1xLe9t6g8L3A+CjxwPsHuZHBbaV3OqsewabXEtcO31sbazfs8L3A+CjxwPsTHw7Q8L3A+CjxwPjxpbWcgc3JjPQ=="http://www.2cto.com/uploadfile/Collfiles/20140824/20140824090454221.png" alt="\">

顯然這題

考慮一下變換記分的方式

我們有

那麼記分方式就變為

一段連續的O，有多少對O×2+O的個數

一對O可以貢獻2分

現在得分來源變為兩個地方

一對O（2分），和單個O（1分）

我們知道

期望=概率×收益

我們找到每個對O的概率×2

再找到單個O×出現概率

求和即是期望得汾喎?http://www.Bkjia.com/kf/yidong/wp/" target="_blank" class="keylink">WPC9wPgo8cD48YnI+CjwvcD4KPHA+ttTT2sSz0ru49rXjaTwvcD4KPHA+09AoMSxpKSAoMixpKSAoMyxpKSAoNCxpKS4uLihpLTEsaSnV4tCpttRPo6zDv7j2uMXCyry0yse009fztb3T0sGss8ujrLHIyOc8aW1nIHNyYz0="http://www.2cto.com/uploadfile/Collfiles/20140824/20140824090454225.png" alt="\">

令這些概率和為dp[i],即

這樣我們有遞推關系

對i+1點來說，

dp求和即是所有對O出現的概率之和×2

+

單個O出現的概率×1

求得的即是期望分數

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int NN=111111;
double f[NN];
double dp[NN];
int main(){
#ifndef ONLINE_JUDGE
	freopen("/home/rainto96/in.txt","r",stdin);
#endif

	int n;scanf("%d",&n);
	double sum=0;
	for(int i=1;i<=n;i++){
		//cin>>f[i];
		scanf("%lf",&f[i]);
		sum+=f[i];
	}
	double ansum=0;
	for(int i=2;i<=n;i++){
		dp[i]=(dp[i-1]+f[i-1])*f[i];
		ansum+=dp[i];
	}
	printf("%f\n",ansum*2.0+sum);
}