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

HDU2955 Robberies

最重要的是找动态转移方程,可以将所用银行里的钱看作背包容量,每一家银行的钱看作重量,

不被抓到的概率看作价值,则转移方程为:dp[ j ]=max( dp[ j ] , dp[  j - bag[ i ].v]*( 1- bag[ i ].p ) );

[cpp]
#include<iostream> 
#include<cstdio> 
using namespace std; 
#define max(a,b) (a)>(b)?(a):(b) 
double dp[10010]; 
struct node 

    int v; 
    double p; 
}bag[10010]; 
int main() 

    int T,i,j,n,sum; 
    double p; 
    scanf("%d",&T); 
    while(T--) 
    { 
        scanf("%lf%d",&p,&n); 
        sum=0; 
        for(i=0;i<n;i++) 
        { 
            scanf("%d%lf",&bag[i].v,&bag[i].p); 
            sum+=bag[i].v; 
        } 
        memset(dp,0,sizeof(dp)); 
        dp[0]=1; 
        for(i=0;i<n;i++) 
            for(j=sum;j>=bag[i].v;j--) 
                dp[j]=max(dp[j],dp[j-bag[i].v]*(1-bag[i].p)); 
            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
部分文章来自网络,