深圳建站公司是如何做好营销型网站的,wordpress 官网模板,前端培训找不到工作的多吗,南京小程序制作开发守卫挑战
金牌导航 期望-9
题目大意
有n个数#xff0c;到第i个数#xff0c;有p_i的概率选择这个数#xff0c;问你最后选了最少L个数#xff0c;且选的数的和再加k大于等于0
样例输入
3 1 0
10 20 30
-1 -1 2样例输出
0.300000数据范围 0⩽k⩽20000\leqslant k\leq…守卫挑战
金牌导航 期望-9
题目大意
有n个数到第i个数有p_i的概率选择这个数问你最后选了最少L个数且选的数的和再加k大于等于0
样例输入
3 1 0
10 20 30
-1 -1 2样例输出
0.300000数据范围
0⩽k⩽20000\leqslant k\leqslant 20000⩽k⩽2000 0⩽L⩽n⩽2000\leqslant L \leqslant n\leqslant 2000⩽L⩽n⩽200 −1⩽ai⩽1000-1\leqslant a_i\leqslant 1000−1⩽ai⩽1000 0⩽pi⩽1000\leqslant p_i \leqslant 1000⩽pi⩽100
解题思路
设fi,j,kf_{i,j,k}fi,j,k为前i个数选了j个且数的和为k的期望值 那么有 fi,j,kfi−1,j,k×(1−pi)f_{i,j,k} f_{i - 1,j,k} \times (1 - p_i)fi,j,kfi−1,j,k×(1−pi) fi,j,kfi−1,j−1,k−a[i]×pif_{i,j,k} f_{i - 1,j - 1,k - a[i]} \times p_ifi,j,kfi−1,j−1,k−a[i]×pi 直接dp即可
代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define g(x) (x 200)//使所有数大于0方便存储
#define max(x, y) ((x)(y)?(x):(y))
using namespace std;
int n, l, K, a[210];
double ans, p[210], f[210][210][450];
int main()
{scanf(%d%d%d, n, l, K);for (int i 1; i n; i){scanf(%lf, p[i]);p[i] / 100.0;}for (int i 1; i n; i)scanf(%d, a[i]);f[0][0][g(K)] 1.0;for (int i 1; i n; i)for (int j 0; j i; j){for (int k -200; k 200; k){f[i][j][g(k)] f[i - 1][j][g(k)] * (1.0 - p[i]);if (j 0 -200 k - a[i] k - a[i] 200) f[i][j][g(k)] f[i - 1][j - 1][g(k - a[i])] * p[i]; //dp}for (int k max(-200, 200 - a[i]); k 200; k)f[i][j][401] f[i - 1][j - 1][g(k)] * p[i];//高于200的不可能再变成负数就计算到一起f[i][j][401] f[i - 1][j][401];}for (int i l; i n; i)for (int j 0; j 201; j)ans f[n][i][g(j)];//计算结果printf(%.6lf, ans);return 0;
}
