首页 > 代码库 > zoj 3812 We Need Medicine(01背包)
zoj 3812 We Need Medicine(01背包)
题目链接: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 <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
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<ll, int> 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]]<<W[i]) & bit);
for (ll k = s[j]^v; k != 0; k -= lowbit(k))
dp[j][G[lowbit(k)]] = i;
}
}
}
int main () {
for (int i = 0; i <= 50; i++)
G[1LL<<i] = i;
int cas;
scanf("%d", &cas);
while (cas--) {
init();
int x, y;
while (Q--) {
scanf("%d%d", &x, &y);
if (dp[y][x]) {
int u = dp[y][x];
printf("%d", u);
while (u) {
y -= T[u];
x -= W[u];
u = dp[y][x];
if (u)
printf(" %d", u);
}
printf("\n");
} else
printf("No solution!\n");
}
}
return 0;
}
zoj 3812 We Need Medicine(01背包)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。