HDU1203 I NEED A OFFER! 动态规划 01背包

博客里面还有以前写的解题报告，表示没看懂。这里直接计算其没有被录取的概率，每次去小的值即可

代码如下：

#include <cstring>
#include <cstdio>
#include <cstdlib>
#define MAXN 1005
using namespace std;

int N, M, s[MAXN];
double p[MAXN], dp[10005];

inline double min(double x, double y)
{
    return x < y ? x : y;
}

void zobag(int x)
{
    for (int i = N; i >= s[x]; --i) {
        dp[i] = min(dp[i], dp[i-s[x]]*p[x]);
    } 
}

double DP()
{
    for (int i = 1; i <= M; ++i) {
        zobag(i);
    }
    return 100-100*dp[N];
}

int main()
{
    while (scanf("%d %d", &N, &M), N|M) {
        for (int i = 0; i <= N; ++i) {
            dp[i] = 1;
        }
        for (int i = 1; i <= M; ++i) { 
            scanf("%d %lf", &s[i], &p[i]);
            p[i] = 1.0-p[i];
        } 
        printf("%.1lf%%\n", DP());
    }
    return 0;
}