AHSOFNU NOIP模拟题-13 T2(概率DP)

设$dp(i,j,k)$为前$i$个挑战赢了$j$场,当前背包容量为$k$的状态存在的概率。
注意,背包容量超过$n$即无意义,所以要一直取$min$
状态转移方程:
$dp(i+1,j,k)=dp(i,j,k) \times (1 - P_{i+1})$
$dp(i+1,j+1,k+a_{i+1})=dp(i,j,k) \times P_{i+1}$
在转移的过程中不要忘了取$min$。
我们在DP前需要把挑战按背包容量排序,这样先打掉背包多的怪物,再打要装碎片的怪物,可以避免本来够但安排不合理,而不够背包装碎片的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define FN2 "guard"
using namespace std;
const int MAXN = 200 + 5;
db dp[MAXN][MAXN][MAXN];
struct data {
int ai;
db pi;
bool operator < (const data &b) const {
return ai > b.ai;
}
}a[MAXN];
int n, L, K;
void clean() {
ms(dp, 0);
}
void solve() {
clean();
for (int i=1;i<=n;i++) scanf("%lf", &a[i].pi), a[i].pi /= 100.0;
for (int i=1;i<=n;i++) scanf("%d", &a[i].ai);
sort(a + 1, a + 1 + n);
dp[0][0][min(K, n)] = 1.0;
for (int i=0;i<=n;i++) {
for (int j=0;j<=i;j++) {
for (int k=0;k<=n;k++) {
dp[i + 1][j][k] += dp[i][j][k] * (1 - a[i + 1].pi);
int t = min(k + a[i + 1].ai, n);
if (t < 0) continue;
dp[i + 1][j + 1][t] += dp[i][j][k] * a[i + 1].pi;
}
}
}
db ans = 0.0;
for (int i=L;i<=n;i++) {
for (int j=0;j<=n;j++) {
ans += dp[n][i][j];
}
}
printf("%.6f\n", ans);
}
int main() {
freopen(FN2".in", "r", stdin); freopen(FN2".out", "w", stdout);
scanf("%d%d%d", &n, &L, &K), solve();
fclose(stdin); fclose(stdout);
return 0;
}

守卫者的挑战
(guard.pas/c/cpp)
题目描述
打开了黑魔法师 Vani 的大门,队员们在迷宫般的路上漫无目的地搜寻着关押 applepi 的
监狱的所在地。突然,眼前一道亮光闪过。“我, Nizem,是黑魔法圣殿的守卫者。如果你
能通过我的挑战,那么你可以带走黑魔法圣殿的地图„„”瞬间,队员们被传送到了一个擂
台上,最初身边有一个容量为 K 的包包。
擂台赛一共有 N 项挑战,各项挑战依次进行。第i 项挑战有一个属性 ai ,如果ai   ,
表示这次挑战成功后可以再获得一个容量为 ai 的包包;如果 ai  ,则表示这次挑战成功
后可以得到一个大小为 1 的地图残片。地图残片必须装在包包里才能带出擂台,包包没有
必要全部装满,但是队员们必须把获得的所有的地图残片都带走(没有得到的不用考虑,只
需要完成所有 N 项挑战后背包容量足够容纳地图残片即可),才能拼出完整的地图。并且他
们至少要挑战成功 L 次才能离开擂台。
队员们一筹莫展之时,善良的守卫者 Nizem 帮忙预估出了每项挑战成功的概率,其中
第 i 项挑战成功的概率为

pi 。现在,请你帮忙预测一下,队员们能够带上他们获得的地图
残片离开擂台的概率。
输入格式
第一行三个整数 N , L , K 。
第二行 N 个实数,第i 个实数 pi 表示第i 项挑战成功的百分比。
第三行 N 个整数,第i 个整数 ai 表示第i 项挑战的属性值.
输出格式
一个整数,表示所求概率,四舍五入保留 6 位小数。
样例输入 1
3 1 0
10 20 30
-1 -1 2
样例输出 1
0.300000样例输入 2
5 1 2
36 44 13 83 63
-1 2 -1 2 1
样例输出 2
0.980387
样例说明
在第一个样例中, 若第三项挑战成功,如果前两场中某场胜利,队员们就有空间来容纳
得到的地图残片,如果挑战失败,根本就没有获得地图残片,不用考虑是否能装下;若第三
项挑战失败,如果前两场有胜利,没有包来装地图残片,如果前两场都失败,不满足至少挑
战成功 L 次(L 1)的要求。因此所求概率就是第三场挑战获胜的概率。
数据范围与约定
对于 100% 的数据,保证  K  ,   N  ,  ai  ,   L  N ,
  
p

------ 本文结束 ------