1 条题解

  • -1
    @ 2023-1-31 22:13:18
    #include <bits/stdc++.h>
    #define maxn 210
    using namespace std;
    int n, L, K, s, a[maxn];
    double p[maxn], dp[2][maxn][maxn << 1], ans;
    inline int read(){
    	int s = 0, w = 1;
    	char c = getchar();
    	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
    	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
    	return s * w;
    }
    int main(){
    	n = read(), L = read(), K = read();
    	s = K;
    	for (int i = 1; i <= n; ++i) p[i] = 1.0 * read() / 100;
    	for (int i = 1; i <= n; ++i) s += max(0, a[i] = read());
    	dp[0][0][n + K] = 1;
    	s = n;
    	for (int i = 1; i <= n; ++i){
    		int now = i & 1, pre = now ^ 1;
    		for (int j = 0; j <= i; ++j)
    			for (int k = 0; k <= n + s; ++k) dp[now][j][k] = 0;
    		for (int j = 0; j <= i - 1; ++j){
    			for (int k = 0; k < n + s; ++k) if (dp[pre][j][k] > 0){
    				dp[now][j][k] += dp[pre][j][k] * (1.0 - p[i]);
    				if (k + a[i] >= 0 && k + a[i] < n + s) dp[now][j + 1][k + a[i]] += dp[pre][j][k] * p[i];
    			}
    		}
    	}
    	int now = n & 1;
    	for (int i = n; i < n + s; ++i)
    		for (int j = L; j <= n; ++j) ans += dp[now][j][i];
    	memset(dp, 0, sizeof(dp));
    	dp[0][0][n + K] = 1;
    	for (int i = 1; i <= n; ++i){
    		int now = i & 1, pre = now ^ 1;
    		for (int j = 0; j <= i; ++j)
    			for (int k = 0; k <= n + s; ++k) dp[now][j][k] = 0;
    		for (int j = 0; j <= i - 1; ++j)
    			for (int k = 0; k <= n + s; ++k) if (dp[pre][j][k] > 0){
    				dp[now][j][k] += dp[pre][j][k] * (1.0 - p[i]);
    				if (k + a[i] >= n + s || k >= n + s) dp[now][j + 1][n + s] += dp[pre][j][k] * p[i];
    				else if (k + a[i] < n + s && k + a[i] >= 0) dp[now][j + 1][k + a[i]] += dp[pre][j][k] * p[i]; 
    			}
    	}
    	now = n & 1;
    	for (int i = L; i <= n; ++i) ans += dp[now][i][n + s];
    	printf("%.6lf\n", ans);
    	return 0;
    }
    

    代码不好看,请各位大佬将就一下

    • 1

    信息

    ID
    143
    时间
    1000ms
    内存
    128MiB
    难度
    5
    标签
    递交数
    15
    已通过
    14
    上传者