学步园

题目分析：定义dp[i][j]申请前i家学校，花费j，一家都没申请上的最小概率

显然dp[i][j]=min(dp[i-1][j],dp[i-1][j-w[i]]*(1-p[i]));

初始化：dp[i]=1;(0<=i<=n)

#include<iostream>
#include<cstdio>
using namespace std;
double dp[10010],p[1010];
int w[1010];
int main()
{
    int n,m;
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		if(n==0&&m==0)
			break;
		for(int i=1;i<=m;i++)
			scanf("%d %lf",&w[i],&p[i]);
		for(int i=0;i<=10000;i++)
			dp[i]=1;
		dp[0]=1;
		for(int i=1;i<=m;i++)
			for(int j=n;j>=w[i];j--)//开始写错了
				dp[j]=min(dp[j],dp[j-w[i]]*(1-p[i]));
		//double temp=1;
		/*for(int i=0;i<=n;i++)
			if(temp>dp[i])
				temp=dp[i];*/
		double ans=(1-dp[n])*100;
		printf("%.1lf%%\n",ans);
	}
	system("pause");
	return 0;
}