希望的海洋

Ain't about how fast I get there,ain't about what's waiting on the other side

常用链接

统计

最新评论

selective1_2_g 01背包 hdu 2955

 

简单的01背包,直接做有点麻烦,可以转化为在大于逃脱率的情况下可以获得的最大钱数也就是求得到某个钱数时的最大逃脱率,状态转移方程是 dp[j]=max(dp[j],dp[j-s[i].m]*s[i].p)

初值dp[0]=1 ,因为不偷钱当然是不被抓的,这里的dp[j]就是获得j钱数可以达到的最大逃脱率!几次抢劫必须同时逃脱才可以,因此概率要乘!这里有个常数级的优化,可以用sum[i] 记录前i的银行(包括i)的钱数和,这样第二个循环就可以是for(j = sum[i] ; j>=s[i].m;j--) , 因为当j >sum[i] 时 j-s[i].m>sum[i-1] (sum[i]-sum[i-1]=s[i].m)这时的dp[j-s[i].m]显然还没有算出来,因为此时最多只算到了sum[i-1] !

#include<iostream>
#include<math.h>
#define M 105
using namespace std;

struct ss {
    double p;
    int m;
} s[M];

int main() {
    int t, i, j, n, sum[M];
    double dp[M * M], P;
    scanf("%d", &t);
    while (t-- && scanf("%lf %d", &P, &n)) {
        P = 1 - P;
        memset(dp, 0, sizeof (dp));
        dp[0] = 1;
        sum[0] = 0;
        for (i = 1; i <= n; i++) {
            scanf("%d %lf", &s[i].m, &s[i].p);
            s[i].p = 1 - s[i].p;
            sum[i] = sum[i - 1] + s[i].m;
        }
        for (i = 1; i <= n; i++)
            for (j = sum[n]; j >= s[i].m; j--)
                dp[j] = max(dp[j], dp[j - s[i].m] * s[i].p);
        for (j = sum[n]; j >= 1; j--)
            if (dp[j] > P)break;
        printf("%d\n", j);
    }
    return 0;
}

posted on 2011-09-18 10:30 拥梦的小鱼 阅读(262) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理