1 条题解

  • 0
    @ 2023-9-24 15:24:39
    #include<bits/stdc++.h>
    using namespace std;
    const int N = 10010;
    int a[N];
    double b[N];
    double dp[2][N];
    int main(){
    	freopen("offer.in","r",stdin);
    	freopen("offer.out","w",stdout); 
    	int n, m;
    	cin >> n >> m;
    	for (int i = 1; i <= m; i ++){
    		cin >> a[i] >> b[i];
    		b[i] = 1 - b[i];
    	}
    	bool flag = 1;
    	for (int i = 0; i <= n; i ++) dp[0][i] = 1;
    	for (int i = 1; i <= m; i ++){
    		for (int j = 0; j <= n; j++){
    			if(j >= a[i]){
    				dp[flag][j] = min(dp[1-flag][j], dp[1-flag][j-a[i]] * b[i]);
    			}else{
    				dp[flag][j] = dp[1-flag][j];
    			}
    		}
    		flag = 1 - flag;
    	}
    	printf("%.1f%%", (1-dp[1-flag][n]) * 100);
    	return 0;
    }
    
    • 1

    信息

    ID
    505
    时间
    1000ms
    内存
    256MiB
    难度
    7
    标签
    (无)
    递交数
    93
    已通过
    25
    上传者