学步园

小记：1A

思路：dp,dp[v] 表示v万美金不能拿到一份工作的概率

dp[v] = min(dp[v], dp[v-a[i].v] * a[i].t （v∈(0,n], i∈[1,m]）

a[i].v表示第i所学校所需的美金， a[i].t表示失败的概率

最后的answer就是(1- min（dp[v]）) (v ∈[0,n])

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>

using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))
#define eps 10e-8

const int MAX_ = 10010;
const int N = 100010;
const int INF = 0x7fffffff;

struct node{
    int v;
    double t;
}a[MAX_];

double dp[MAX_];

int main(){
	int n, m;
	double k, ans;
	while(~scanf("%d%d",&n, &m), n||m){
        for(int i = 0; i < m; ++i){
            scanf("%d%lf",&a[i].v, &k);
            a[i].t = 1.0 - k;
        }
        for(int i = 0; i <= n; ++i){
        	dp[i] = 1;
        }
        for(int i = 0; i < m; ++i){
            for(int v = n; v >= a[i].v; --v){
                dp[v] = min(dp[v], dp[v-a[i].v] * a[i].t);
            }
        }
        ans = INF;
        for(int i = 0; i <= n; ++i){
        	ans = min(ans, dp[i]);
        }

        printf("%.1f%%\n", (1.0 - ans)*100);


	}
	return 0;
}