HDU 1203 I NEED A OFFER!

此题一定要注意输入是 n || m 不是 n&&m, 就因为这个WA了几次

此题是01背包的增加型，不要完全套01背包，由于是概率所以要考虑乘法，题目要求的是至少被录取，根据概率论，求其反面简单

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 #include <cstdio>
 5 #include <cstring>
 6 
 7 using namespace std;
 8 
 9 int main(){
10     int n,m;
11     while(cin >> n >> m && (n || m)){
12         vector<int> cost(m);
13         vector<double> prob(m);
14         for(int i= 0 ; i < m ; i ++ ) cin >>cost[i]>>prob[i];
15         vector<double> dp(n+1,1.0);
16         for(int i = 0 ; i < m; i ++ ){
17             for(int j = n; j >= cost[i]; j -- ){
18                 dp[j] = min(dp[j] , dp[ j - cost[i] ]*(1.0- prob[i]) );
19             }
20         }
21         printf("%.1lf%%\n",(1-dp[n])*100);
22     }
23     return 0;
24 }

注意memset只能将数组初始化 0或 -1，不能用于初始化话其它值，如果想将数组初始化可以利用

　　fill ( dp, dp+n, 1);