【BZOJ3029】守卫者的挑战-526互联

题目

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

int N, L, K;
double f[210][210][210];
//这里一定要注意，因为有用的容量至多为N，所以只用开N个 

struct Level {
	int a;
	double p;
}level[521];

bool cmp(const Level &a, const Level &b) {
	if (a.a != b.a) return a.a > b.a;
	else return false;
}

int main() {
	scanf("%d%d%d", &N, &L, &K);
	for (int i = 1, read; i <= N; ++ i) {
		scanf("%d", &read);
		level[i].p = (read * 1.0) / 100.0;
	}
	for (int i = 1; i <= N; ++ i) {
		scanf("%d", &level[i].a);
	}
	sort(level + 1, level + 1 + N, cmp);
	//排序是为了让dp的时候先把背包容量加到有用的最满 
	f[0][0][min(N, K)] = 1;
	for (int i = 1; i <= N; ++ i) {
		for (int j = 0; j <= i; ++ j) {
			for (int k = 0; k <= N; ++ k) {
				f[i][j][k] += f[i - 1][j][k] * (1 - level[i].p);
				if (k + level[i].a >= 0 && j != 0) {
					//只用管背包容量大于0的概率就行了 
					f[i][j][min(N, k + level[i].a)] += f[i - 1][j - 1][k] * level[i].p;
					//这里面的k表示前一状态 
				}
			}
		}
	}
	double ans = 0; 
	for (int j = L; j <= N; ++ j) {
		for (int k = 0; k <= N; ++ k) { 
			ans += f[N][j][k];
		}
	}
	printf("%.6lf", ans);
	return 0;
}

BZOJ

3029