守衛挑戰

金牌導航 期望-9

題目大意

有n個數，到第i個數，有p_i的概率選擇這個數，問你最后選了最少L個數，且選的數的和再加k大于等于0

樣例輸入

3 1 0 10 20 30 -1 -1 2

樣例輸出

0.300000

數據范圍

$0?k?2000$
$0?L?n?200$
$?1?a_i?1000$
$0?p_i?100$

解題思路

設$f_{i,j,k}$為前i個數，選了j個，且數的和為k的期望值
那么有：
$f_{i,j,k}=f_{i?1,j,k}\times (1?p_i)$
$f_{i,j,k}+=f_{i?1,j?1,k?a[i]}\times p_i$
直接dp即可

代碼

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #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; }

總結

以上是生活随笔為你收集整理的【期望】守卫挑战（金牌导航 期望-9）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。