B - I NEED A OFFER! （背包）
后面的m行，每行都有两个数据ai(整型),bi(实型)分别表示第i个学校的申请费用和可能拿到offer的概率。
输入的最后有两个0。
Output每组数据都对应一个输出，表示Speakless可能得到至少一份offer的最大概率。用百分数表示，精确到小数点后一位。
Sample Input
10 3 4 0.1 4 0.2 5 0.3 0 0Sample Output
44.0%
int main(){
int money,price[10005],n;
double possible[10005],dp[10005];
while(1){
cin>>money>>n; if(money==0&&n==0)break;
for(int i=1;i<=n;i++){
cin>>price[i]>>possible[i];
possible[i]=1.0-possible[i];
}
//dp[j]:有j万元时前i个学校都不录取的最小概率；
for(int s=0;s<=money;s++){ //不能写（int s=1;s<=money;s++) 会wa的
dp[s]=1;
}
for(int i=1;i<=n;i++){
for(int j=money;j>=price[i];j--){
dp[j]=dp[j]<dp[j-price[i]]*possible[i] ? dp[j]:dp[j-price[i]]*possible[i];
}
}
printf("%.1lf%%\n",(1-dp[money])*100);
}
return 0;
}
/*
10 3
4 0.1
4 0.2
5 0.3
*/
注意！
本站转载的文章为个人学习借鉴使用，本站对版权不负任何法律责任。如果侵犯了您的隐私权益，请联系我们删除。