HDU 1203 I NEED A OFFER! 01背包

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

解题思路：简单的01背包，用dp[i]表示花费不超过i时的最大可能性

状态转移方程 dp[i]=1-(1-dp[i-a])*(1-p)

 1 #include<cmath>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 using namespace std;
 7 #define N 10001
 8 int n,m;
 9 double dp[N];
10 int main()
11 {
12     int i,a,j;
13     double p,pp;
14     while(scanf("%d%d",&n,&m),n||m)
15     {
16         memset(dp,0,sizeof(dp));
17         for(i=0;i<m;i++)
18         {
19             scanf("%d%lf",&a,&p);
20             for(j=n;j>=a;j--)
21             {
22                 pp=1-(1-dp[j-a])*(1-p);
23                 dp[j]=max(dp[j],pp);
24             }
25         // for(int k=1;k<=n;k++)cout<<dp[k]<<' ';cout<<endl;
26         }
27         p=dp[n]*100;
28         printf("%.1lf%%
",p);
29     }
30     return 0;
31 }

View Code