概率

http://oj.acm.zstu.edu.cn/JudgeOnline/problem.php?id=4439

C++版本一

题解：

概率背包问题

套模板就行，emmm max改成min计算不能中奖的概率

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG

using namespace std;
typedef long long ll;
const int N=1000+10;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m;
int a[N];
double b[N];
double dp[N];
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    while(~scanf("%d%d",&n,&m)){
        for(int i=1;i<=n;i++){
            scanf("%d%lf",&a[i],&b[i]);
            b[i]=1-b[i];
        }
        for(int i=0;i<=m;i++){
            dp[i]=1;
        }
        for(int i=1;i<=n;i++){
            for(int j=m;j>=a[i];j--){
                dp[j]=min(dp[j],dp[j-a[i]]*b[i]);
            }
        }
        printf("%.4f\n",1-dp[m]);
    }

    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

题解：

这题求一个中奖的最大概率可以转换为求一次都没有中奖的概率，然后用1减去这个概率就是中奖的概率；那么就可以转换成背包问题，维护一个最小的不中奖的概率；也就是dp【j】 = min(dp【j】,dp[j-a[i]]*pi[i]); pi[i]是不中奖的概率

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+5;
double dp[N],pi[N];
int a[N];
int main()
{
//    freopen("data.in","r",stdin);
//    freopen("data.out","w",stdout);
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {

        for(int i = 1; i <= n; i ++){
            scanf("%d%lf",&a[i],&pi[i]);
            pi[i] = 1-pi[i];
        }
        for(int i = 0; i <= m; i ++) dp[i] = 1;
        for(int i = 1; i <= n; i ++){
            for(int j = m; j >= a[i]; j --){
                dp[j] = min(dp[j],dp[j-a[i]]*pi[i]);
            }
        }
        printf("%.4f\n",1-dp[m]);
    }


    return 0;
}

C++版本三

#include<bits/stdc++.h>
using namespace std;
double dp[10005][10005];
double pi[10005];
int a[10005];
int main()
{
//    freopen("data.in","r",stdin);
//    freopen("text1.out","w",stdout);
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        for(int i = 1; i <= n; i ++){
            scanf("%d%lf",&a[i],&pi[i]);
            pi[i] = 1-pi[i];
        }
        for(int i = 0; i <= m; i ++)dp[0][i] = 1;
        for(int i = 1; i <= n; i ++){
            for(int j = 0; j < a[i]; j ++) dp[i][j] = dp[i-1][j];
            for(int j = a[i]; j <= m; j ++)
                dp[i][j] = min(dp[i-1][j],dp[i-1][j-a[i]]*pi[i]);
        }
        printf("%.4f\n",1-dp[n][m]);


    }

    return 0;
}

C++版本四

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;

double dp[N];

int main()
{
//    freopen("data.in", "r", stdin);
//    freopen("check1.out", "w", stdout);
    int n, m;
    while(~scanf("%d%d", &n, &m)){
        for(int i = 0; i <= m; ++i) dp[i] = 0.0;
        int x;
        double p;
        for(int i = 1; i <= n; ++i){
            scanf("%d%lf", &x, &p);
            for(int i = 0; i <= m - x; ++i){
                dp[i] = max(dp[i], dp[i + x] + (1 - dp[i + x]) * p);
            }
        }
        printf("%.4f\n", dp[0]);
    }
    return 0;
}