牛客网练习赛26B(简单的dp)

题目链接：https://www.nowcoder.com/acm/contest/180/B

链接：https://www.nowcoder.com/acm/contest/180/B
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
Special Judge, 64bit IO Format: %lld

题目描述

小a有个烟花，每个烟花代表着互不相同的颜色，对于第个烟花，它有的概率点燃，现在小a要去点燃它们，他想知道产生颜色的期望个数 及 产生恰好产生种颜色的概率

输入描述:

第一行两个整数

接下来一行

个数，第

个数

表示第

个烟花被点燃的概率

输出描述:

输出有两行
第一行表示产生不同颜色的期望个数

第二行表示产生恰好种颜色的概率
以换行符分割
 

<!--
-->

输入例子:

3 2

0.5 0.25 0.75

输出例子:

1.5000

0.4062

-->

示例1

输入

复制

3 2

0.5 0.25 0.75

输出

复制

1.5000

0.4062

说明

第二问样例解释：

相加得

备注:

对于

的数据：

对于

的数据：

输出均保留4位小数,若你的答案误差与std不超过

即为正确

具体思路看代码

#include<iostream>

#include<string.h>

#include<map>

#include<cstdio>

#include<cstring>

#include<stdio.h>

#include<cmath>

#include<ctype.h>

#include<math.h>

#include<algorithm>

#include<set>

#include<queue>

typedef long long ll;

using namespace std;

const ll mod=1e9+;

const int maxn=1e5+;

const int maxk=5e3+;

const int maxx=1e4+;

const ll maxe=+;

#define INF 0x3f3f3f3f3f3f

#define Lson l,mid,rt<<1

#define Rson mid+1,r,rt<<1|1

double a[maxn],b[][maxn];//b[i][j]代表前i个烟花，选了j个的概率,需要用到滚动数组，因为n的范围太大，开二维会爆

int main()

{

    double sum=;

    int n,k,p=;

    scanf("%d%d",&n,&k);

    //cin>>n>>k;

    for(int i=;i<=n;i++)

    {

        cin>>a[i];

        sum+=a[i];

    }

    b[][]=-a[];

    b[][]=a[];

    for(int i=;i<=n;i++)

    {

        p^=;

        for(int j=;j<=min(i,k);j++)

        {

            if(j==)

            {

                b[p][j]=b[p^][j]*(-a[i]);

            }

            else

            {

                b[p][j]=b[p^][j-]*a[i]+b[p^][j]*(-a[i]);//前i-1个选了j个则当前的不选，前i-1个选了j-1个，则当前的选

            }

        }

    }

    printf("%.4lf\n",sum);

    printf("%.4lf\n",b[p][k]);

}

牛客网练习赛26B(简单的dp)的相关教程结束。