I NEED A OFFER!

题目链接：https://vjudge.net/contest/395099#problem
 1 #include <iostream>
 2 #include <algorithm> 
 3 #include <cstring>
 4 using namespace std;
 5 
 6 const int maxn = 1e5;
 7 
 8 struct node
 9 {
10     int w;
11     double val;
12 }arr[maxn];
13 
14 double dp[maxn];
15 
16 double getN(double a, double b)
17 {
18     double t1 = 1 - a, t2 = 1 - b;
19     return 1 - t1 * t2;
20 }
21 
22 int main()
23 {
24     int n, m;
25     while (~scanf("%d %d", &n, &m))
26     {
27         if(n == 0 && m == 0) break;
28         memset(dp, 0, sizeof(dp));
29         for (int i = 1; i <= m; i++) scanf("%d %lf", &arr[i].w, &arr[i].val);
30         for (int i = 1; i <= m; i++)
31         {
32             for (int j = n; j >= arr[i].w; j--)
33             {
34                 dp[j] = max( getN(dp[j - arr[i].w], arr[i].val), dp[j]);
35             }
36         }
37         printf("%.1f%%
", dp[n] * 100);
38     }
39     return 0;
40 }