ZOJ 3812 We Need Medicine - c++编程基础

TOP

ZOJ 3812 We Need Medicine

2015-07-20 17:40:09 来源: 作者: 【大中小】浏览:2次

Tags：ZOJ 3812 Need Medicine

题意：

一个物品重w效力t 给出所有n个物品有q个询问每个询问输出w的和为m同时t的和为s的方案

思路：

明显就是01背包只不过一个东西在两个维度上有价值由于w只有50因此可以状压

先想如何输出方案利用f[i][j]表示sumw=i同时sumt=j时候装进包里的最后一个物品那么输出这个物品后i和j都减去这个物品的w和t 就可以到达新的状态这样可以一直到背包为空最多循环50次

最难得是dp过程之前提到状压这题精髓就是状压后50位状态一起转移用g[i]表示sumt=i时包含的sumw 对于一个重w效力t的物体 g[i]->g[i+t] 同时所有sumw->sumw+w 这样相当于少for了一维然后再把g[i+t]中从0变成1的sumw的f数组对应记录一下

PS：

__builtin_ctz() 从ftiasch代码中看到了这个函数蛮方便的这是对于一个unsigned int返回二进制最后一个1后有几个0 那么__builtin_ctzll()则是针对unsigned long long的

做了3天数模高教社杯比赛累成狗不说刷题节奏完全断了…… 要快点找回感觉…… 补题补题补题补题……

代码：

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
         #include
         
           #include
          
            using namespace std; typedef long long LL; #define Q 401 #define N 51 #define M 200001 #define inf 2147483647 #define lowbit(x) (x&(-x)) int t, n, q; short f[N][M]; LL g[M]; int v[Q], w[Q], aw[Q], av[Q]; int main() { int i, j, fv, fw; LL k, tmp; scanf("%d", &t); while (t--) { memset(f, 0, sizeof(f)); memset(g, 0, sizeof(g)); g[0] = 1; scanf("%d%d", &n, &q); for (i = 1; i <= n; i++) scanf("%d%d", &w[i], &v[i]); for (i = 1; i <= q; i++) scanf("%d%d", &aw[i], &av[i]); for (i = 1; i <= n; i++) { for (j = M - 1; j >= v[i]; j--) { k = ((g[j - v[i]] << w[i]) & ((1LL << N) - 1)) | g[j]; tmp = k ^ g[j]; g[j] = k; while (tmp) { f[__builtin_ctzll(tmp)][j] = i; tmp ^= lowbit(tmp); } } } for (i = 1; i <= q; i++) { fw = aw[i]; fv = av[i]; if (f[fw][fv]) { j = f[fw][fv]; printf("%d", j); fw -= w[j]; fv -= v[j]; for (; fw && fv;) { j = f[fw][fv]; printf(" %d", j); fw -= w[j]; fv -= v[j]; } putchar('\n'); } else puts("No solution!"); } } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：KMP子串搜索算法C语言实现	下一篇：CF 题目集锦 PART 6 # 265 div 1 C

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: