当前位置:编程学习 > C/C++ >>

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++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,