Atcoder DP Contest pI
題敘
https://atcoder.jp/contests/dp/tasks/dp_i
有 $n$ 個硬幣，每個硬幣有翻到正面的機率 $p_i$
問正面多於反面的機率有多少
想法
嘗試遮住最後一個硬幣，觀察每次擲硬幣會影響到哪些
定義 $DP[i]$ 表示有 $i$ 個硬幣為正面的機率
則有轉移式 $DP[i] = DP[i-1]*arr[i] + DP[i]*(1-arr[i])$
且已知 $DP[0] = 1$
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
#include<bits/stdc++.h>
#define LL long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
using namespace std;
int n;
double now,dp[3005];
int main(){
IOS
while(cin>>n){
dp[0]=1;
for(int i=0 ; i<n ; i++){
cin>>now;
for(int j=i+1 ; j>=0 ; j--){
dp[j] = (j==0 ? 0 : dp[j-1]*now) + dp[j]*(1-now);
}
}
double ans=0;
for(int i=n/2+1 ; i<=n ; i++){
ans+=dp[i];
}
cout<<fixed<<setprecision(10)<<ans<<"\n";
}
return 0;
}
|
複雜度
有 $n$ 種狀態，每種狀態轉移複雜度約為 $O(n)$
總複雜度 $O(n^2)$