Hint

Bài này thực ra có 3 cách để quy hoạch động

Cách 1

Gọi \(dp[i][j]\) là xác suất khi tung \(i\) đồng xu đầu tiên được \(j\) đồng xu ngửa.

Trường hợp 1: Đồng xu \(i\) là đồng ngửa => Ta cần tính xác suất để tung \(i-1\) đồng đầu tiên được \(j-1\) đồng ngửa. Vậy xác suất cho trường hợp này là \(dp[i-1][j-1] * p[i]\).

Trường hợp 2: Đồng xu \(i\) là đồng sấp => Ta cần tính xác suất để tung \(i-1\) đồng đầu tiên được \(j\) đồng ngửa. Vậy xác suất cho trường hợp này là \(dp[i-1][j] * (1-p[i])\).

Vậy xác suất để tung \(i\) đồng được \(j\) đồng ngửa là \(dp[i-1][j-1] * p[i]+dp[i-1][j]*(1-p[i])\)

Xác suất để tung \(n\) đồng được số đồng ngửa nhiều hơn số đồng sấp là \(dp[n][n/2+1]+dp[n][n/2+2]+...+dp[n][n]\)

AC code

#include<bits/stdc++.h>
using namespace std;
double dp[3005][3005];
int main()
{
    cout.precision(9);
    int n;
    cin>>n;
    double p;
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        cin>>p;
        for(int j=0;j<=i;j++)
            dp[i][j]=dp[i-1][j-1]*p+dp[i-1][j]*(1-p);
    }
    p=0;
    for(int i=n/2+1;i<=n;i++) p+=dp[n][i];
    cout<<p;
}

Cách 2 ##

(Hơi phức tạp hơn tý)

Gọi \(dp[i][j]\) là xác suất khi tung \(i\) đồng xu đầu tiên được số đồng xu ngửa nhiều hơn số đồng xu sấp \(j\) đồng (\(j\) có thể âm).

Trường hợp 1: Đồng xu \(i\) là đồng ngửa => Ta cần tính xác suất để tung \(i-1\) đồng đầu tiên được số đồng ngửa nhều hơn số đồng sấp là \(j-1\) đồng. Vậy xác suất cho trường hợp này là \(dp[i-1][j-1] * p[i]\).

Trường hợp 2: Đồng xu \(i\) là đồng sấp => Ta cần tính xác suất để tung \(i-1\) đồng đầu tiên được số đồng ngửa nhiều hơn số đồng sấp là \(j+1\) đồng. Vậy xác suất cho trường hợp này là \(dp[i-1][j+1] * (1-p[i])\).

Vậy xác suất để tung \(i\) đồng được \(j\) đồng ngửa là \(dp[i-1][j-1] * p[i]+dp[i-1][j+1]*(1-p[i])\)

Xác suất để tung \(n\) đồng được số đồng ngửa nhiều hơn số đồng sấp là \(dp[n][1]+dp[n][2]+...+dp[n][n]\)

AC code

#include<bits/stdc++.h>
using namespace std;
double dp[3005][6005];
int main()
{
    cout.precision(9);
    int n;
    cin>>n;
    dp[0][3000]=1;
    double p;
    for(int i=1;i<=n;i++)
    {
        cin>>p;
        for(int j=-i;j<=i;j++)
            dp[i][j+3000]=dp[i-1][j+2999]*p+dp[(i-1)][j+3001]*(1-p);
    }
    double t=0;
    for(int i=0;i<=n;i++)
        t+=dp[n][i+3000];
    cout<<t;
}

Cách 3

(Khó code nhất nhưng dễ hiểu nhất)

Gọi \(dp[i][j]\) là xác suất khi tung \(i+j\) đồng xu đầu tiên được \(i\) đồng xu ngửa và \(j\) đồng xu sấp.

Trường hợp 1: Đồng xu \(i+j\) là đồng ngửa => Ta cần tính xác suất để tung \(i+j-1\) đồng đầu tiên được \(i-1\) đồng ngửa và \(j\) đồng sấp. Vậy xác suất cho trường hợp này là \(dp[i-1][j] * p[i]\).

Trường hợp 2: Đồng xu \(i+j\) là đồng sấp => Ta cần tính xác suất để tung \(i+j-1\) đồng đầu tiên được \(i\) đồng ngửa và \(j-1\) đồng sấp. Vậy xác suất cho trường hợp này là \(dp[i][j-1] * (1-p[i])\).

Vậy xác suất để tung \(i\) đồng được \(j\) đồng ngửa là \(dp[i-1][j] * p[i]+dp[i][j-1]*(1-p[i])\)

Xác suất để tung \(n\) đồng được số đồng ngửa nhiều hơn số đồng sấp là \(dp[n/2+1][n/2]+dp[n/2+2][n/2-1]+...+dp[n][0]\)

AC code

#include<bits/stdc++.h>
using namespace std;
double dp[3005][3005];
double rat[3005];
int main()
{
    cout.precision(9);
    int n;
    cin>>n;
    double p;
    dp[0][0]=1;
    for(int i=1;i<=n;i++) cin>>rat[i];
    for(int i=0;i<=n;i++)
    {
        for(int j=0+(i==0);j<=n-i;j++)
        {
            double t=dp[i-1][j];
            if(i==0) t=0;
            dp[i][j]=t*rat[i+j]+dp[i][j-1]*(1-rat[i+j]);
        }
    }
    p=0;
    for(int i=n/2+1;i<=n;i++) p+=dp[i][n-i];
    cout<<p;
}

Ghi chú: Ta dùng lệnh cout.precision(9) để lấy đến 9 chữ số sau dấu thập phân.
Độ phức tạp của 3 cách này đều là \(O(N^2)\)