Comment

09022208: 2024-06-05 14:53:55

#include <iostream>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <functional>
double dp[1005];
int odds[1000];
using namespace std;
int main()
{
	int x;
	cin>>x;
	while(x--){
		int n;
		cin>>n;
		for(int i=1;i<n;i++){
			cin>>odds[i];
		}
		dp[0]=1.0;
		for(int i=1;i<n;i++){
			dp[i]=0;
		}
		for(int i=1;i<n;i++){
			for(int j=i;j>=1;j--){
				dp[j]=dp[j]*(100-odds[i])*1.0/100.0+dp[j-1]*odds[i]*1.0/100.0;//从大到小，类似0-1背包问题
			}
			dp[0]=dp[0]*(100-odds[i])*1.0/100.0;
		}
		double ans=0;
		for(int i=0;i<n;i++){
			ans += (i+1) * dp[i];
		}
		printf("%.6lf\n",ans);
	}
	
	return 0;
}

hanser414627925: 2024-05-29 15:27:36

#include<iostream>
#include<math.h>
#include<iomanip>
#include<string.h>
using namespace std;
int main()
{
	int T;
	cin >> T;
	for (int w = 0; w < T; w++)
	{
		int N;
		double EX = 0.0;
		cin >> N;		//1<=N<=1000
		int* p = new int[N];
		double** f = new double*[2];//f[i][j]前i座桥断了j座的概率
		for (int j = 0; j < 2; j++)
			f[j] = new double[N];//f[i][j]：j<=i时有效
		for (int j = 1; j < N; j++)
			cin >> p[j];//断桥的概率
		f[0][0] = 1.0;
		for (int i= 1; i <N; i++)
		{
			f[i%2][0] = f[abs(i%2-1)][0] * (1 - p[i] / 100.0);
			f[abs(i%2-1)][i] = 0.0;
			for (int j = 1; j <= i; j++)
			{
				f[i%2][j] = f[abs(i%2-1)][j] * (1 - p[i] / 100.0) + f[abs(i%2-1)][j - 1] * p[i] / 100.0;
			}
		}
		for (int i = 0; i < N; i++)
			EX += (i + 1) * f[abs(N%2-1)][i];
		cout<<fixed<<setprecision(6)<<EX << endl;
		delete []p;
		for (int j = 0; j < 2; j++)
			delete []f[j];
		delete []f;
	}
	return 0;
}

友利奈绪: 2024-05-28 17:03:48

#include<iostream>
#include<iomanip>
using namespace std;
int main() {
    int m;
    cin >> m;
    while (m--)
    {
        int n;
        cin >> n;
        double res = 100;
        for (size_t i = 0; i < n - 1; i++)
        {
            int p;
            cin >> p;
            res += p;
        }
        res /= 100.0;
        cout <<fixed<<setprecision(6)<< res << endl;
    }
    return 0;
}
本人题解
res=1.0+p1+p2+……+pn

LSLOVE: 2023-05-25 16:18:11

可以用贡献法做题，每一条边对连通块个数的贡献是什么。将贡献概率化就可以了

green_finger: 2023-03-22 16:31:38

求助一下为什么这样不行啊？能过测试用例不能AC。
#include<iomanip>
#include<iostream>
using namespace std;

double p[101];
double dp[1001];

double solve(int n) {
	int i;
	for (int a = 1; a < n; ++a) {
		cin >> i;
		p[a] = i / 100.0;
	}
	//memset(dp,0,n*sizeof(double));
	dp[0] = 1.0;
	for (int a = 1; a < n; ++a)
		dp[a] = 0.0;
	for (int b = 1; b < n; ++b) {
		for (int a = b; a > 0; --a) {
			dp[a] = dp[a] * (1.0 - p[b]) + dp[a - 1] * p[b];
		}
		dp[0] *= (1.0 - p[b]);
	}
	double sum = 1.0;
	for (i = 1; i < n; ++i) {
		sum += i * dp[i];
	}
	return sum;
}
int main() {
	int nums;
	cin >> nums;
	double* out = new double[nums];
	for (int a = 0; a < nums; ++a) {
		int n;
		cin >> n;
		out[a] = solve(n);
	}
	for (int a = 0; a < nums; ++a)
		cout << fixed << setprecision(6) << out[a] << endl;
	delete[]out;
	return 0;
}

huangteng: 2022-11-24 11:51:04

输出\sum p_i +1

周志华亲传弟子: 2021-11-18 17:09:23

给个时间O(n)空间O(1)的思路：注意到每座桥断与不断都是相互独立的，而连通分量的增加量相对于桥断不断是固定的，即桥断分量数加1，不断就不增加。因此可以等价为以下问题：抛掷n-1个硬币，给定每个硬币正面朝上的概率，硬币正面朝上则得到1的reward，初始reward为1，求最终得到的reward期望。（考虑一下随机变量期望的可加性）

算法学习1号机: 2021-11-02 16:01:51

注意memory很小，只有1000KB，如果开double类型二维数组容易超过范围，需要空间复杂度优化。