hdu 2955 Robberies（01背包）点击打开链接题目意思：01背包的简单变异。。dp[i]表示偷取i元不被抓的概率。。。dp[
hdu 2955 Robberies（01背包）
点击打开链接
题目意思：
01背包的简单变异。。
dp[i]表示偷取i元不被抓的概率。。。
dp[j]=max(dp[j]，dp[j-mm[i]]*(1-pp[i])）
#include"stdio.h"#include"string.h"#define max(x,y) x>y?x:y;double dp[10001];int main(){int sum,i,j,mm[101],t,n;double p,pp[101];scanf("%d",&t);while(t--){scanf("%lf%d",&p,&n);sum=0;for(i=0;i<n;i++){scanf("%d%lf",&mm[i],&pp[i]);sum+=mm[i];}memset(dp,0,sizeof(dp));dp[0]=1;for(i=0;i<n;i++){for(j=sum;j>=mm[i];j--)dp[j]=max(dp[j],dp[j-mm[i]]*(1-pp[i]));}for(i=sum;i>=0;i--){if(dp[i]>=(1-p)){printf("%d\n",i);break;}}}return 0;}