题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1203

动态规划问题
思考：至少拿到一个offer就是可以拿到1,2,3…个offer的情况，而该情况是 1-不拿offer的情况。
求最大拿offer的概率==求最小不拿offer的概率
具体运算可以看dp变化表（适用于本题样品）

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

int main()
{
    int n,m;
    double dp[10010];
    while(~scanf("%d %d",&n,&m)&&n+m)//n+m是输入0 0的时候输出
    {
        for(int i=0;i<=n;i++)//memset只能初始化int
            dp[i]=1.0;//dp存的是拿不到offer的概率,假设一开始不管多少钱都拿不到

        while(m--)
        {
            int a;
            double b;
            scanf("%d %lf",&a,&b);//申请费用,可能拿到offer的概率

            for(int i=n;i>=a;i--)//凡是小于a的钱都百分百无法报考
                dp[i]=min(dp[i],dp[i-a]*(1-b));//(1-b)是得不到offer的概率
            /*
            dp表变化情况
            for(int i=0;i<=10;i++)
                printf("%.2lf  ",dp[i]);
            printf("\n");
            */
        }
        printf("%.1lf%%\n",(1-dp[n])*100);//至少得到一份就是除掉得不到的概率
    }
    return 0;
}