hdu 1203 I NEED A OFFER!
dp[j]表示用j万元，不能得到一个offer的最小概率。。动态转移方程：dp[j] =min(dp[j],dp[j-a[i]]*b[i])
#include"stdio.h"int a[10010];double b[10010],dp[10010];double min(double x,double y){return x<y?x:y;}int main(){int n,m,i,j;while(scanf("%d%d",&n,&m)!=EOF){if(n==0&&m==0)break;for(i=1;i<=m;i++)scanf("%d%lf",&a[i],&b[i]);for(i=1;i<=m;i++)b[i]=1-b[i];//注意原来的b是能成功的概率，这里要变一下。。for(i=0;i<=n;i++)dp[i]=1;for(i=1;i<=m;i++){for(j=n;j>=a[i];j--){dp[j]=min(dp[j],dp[j-a[i]]*b[i]);}}printf("%.1f%%\n",(1-dp[n])*100);}return 0;}