hdu 2955 Robberies(01背包)
题目意思:
01背包的简单变异。。
dp[i]表示偷取i元不被抓的概率。。。
dp[j]=max(dp[j],dp[j-mm[i]]*(1-pp[i]))
[csharp]
#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;
}
补充:软件开发 , C++ ,