http://acm.hdu.edu.cn/showproblem.php?pid=1203
#include <iostream> #include <algorithm> using namespace std; int main() { int n, m; int i, j; int a[10000]; double b[10000], f[10000], bi; while (cin >> n >> m && (n+m)) { for (i = 0; i < m; i++) { cin >> a[i] >> bi; b[i] = 1 - bi; } memset (f, 0, sizeof(f)); for (i = 0; i < m; i++) for (j = n; j >= a[i]; j--) f[j] = max ( f[j],(1 - (1-f[j - a[i]])* b[i]) ); printf("%.1lf%%\n",(f[n])*100); } return 0; }