http://acm.hdu.edu.cn/showproblem.php?pid=1203
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 int a[20000]; 7 double b[20000],dp[20000]; 8 int n,m; 9 10 int main() 11 { 12 while(scanf("%d%d",&n,&m)!=EOF) 13 { 14 memset(dp,0,sizeof(dp)); 15 if(n==0&&m==0) break; 16 for(int i=1; i<=m; i++) 17 { 18 scanf("%d%lf",&a[i],&b[i]); 19 b[i]=1-b[i]; 20 } 21 for(int i=0; i<=n; i++) 22 { 23 dp[i]=1; 24 } 25 for(int i=1; i<=m; i++) 26 { 27 for(int j=n; j>=a[i]; j--) 28 { 29 dp[j]=min(dp[j],dp[j-a[i]]*b[i]); 30 } 31 } 32 printf("%.1lf%% ",(1-dp[n])*100); 33 } 34 return 0; 35 }