zoj 3812 We Need Medicine(01背包) - c++编程基础

TOP

zoj 3812 We Need Medicine(01背包)

2015-07-20 17:43:02 来源: 作者: 【大中小】浏览:1次

Tags：zoj 3812 Need Medicine 背包

题目链接：zoj 3812 We Need Medicine

题目大意：有n中化学成分，每种成分要么选取重量Wi，获得Ti的TEV值，要么不取，获得0的TEV值。现在对于每种病

毒，要求配置质量为Mi的药物，并且TEV值为Si，求化学成分组成。

解题思路：看了别人的题解，以前居然不知道背包转移可以用二进制。

因为质量总共才50，所以用一个long long的二进制数表示说哪些质量是可祖长的，这样的话只要开一个20W的数组

s，s[i]表示说TEV值为i时质量可以为多少。然后每次在用lowbit处理出新增的可能，用dp[i][j]记录路径。

#include 
   
     #include 
    
      #include 
      #include 
      
        using namespace std; #define lowbit(x) ((x)&(-x)) typedef unsigned long long ull; typedef long long ll; const int maxn = 405; const int maxt = 200000; int N, Q, W[maxn], T[maxn]; short dp[maxt + 5][52]; map
       
         G; ull s[maxt]; void init () { scanf("%d%d", &N, &Q); for (int i = 1; i <= N; i++) scanf("%d%d", &W[i], &T[i]); ull bit = (1LL<<51) - 1; memset(s, 0, sizeof(s)); memset(dp, 0, sizeof(dp)); s[0] = 1; for (int i = 1; i <= N; i++) { for (int j = maxt; j >= T[i]; j--) { ull v = s[j]; s[j] |= ((s[j-T[i]]<


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：POJ 2442-Sequence（heap+k路归并..	下一篇：NSAssert NSCAssert NSParameterA..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: