首页 > 代码库 > ZOJ 3812 We Need Medicine（dp、背包、状态压缩、路径记录）
ZOJ 3812 We Need Medicine（dp、背包、状态压缩、路径记录）
参考：http://blog.csdn.net/qian99/article/details/39138329
参考的链接里说明得很好，注释也很好。。。thanks for sharing
朴素的想法不难，dp[i][j][k]类似背包做法即可。
但朴素思想复杂度过高。
这里主要是用到 dif 那个变量，只枚举新增的集合。
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cmath>#include <vector>#include <set>#include <queue>#include <map>using namespace std;#define MP make_pair#define ll long long#define inf 0x3f3f3f3f#define maxn 100010#define maxm 200010ll sta[200010];int ans[55][200010];map<ll,int>mp;int a[410],b[410];int main(){ for(int i=0;i<=50;++i) mp.insert(MP(1ll<<i,i)); int t,n,q; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&q); memset(sta,0,sizeof(sta)); memset(ans,-1,sizeof(ans)); sta[0] = 1; for(int i=1;i<=n;++i){ scanf("%d%d",a+i,b+i); for(int j=200000;j>=b[i];--j){ ll st = sta[j]; sta[j] |= (sta[j-b[i]]<<a[i]) & ((1ll<<52)-1); ll dif = st^sta[j]; while(dif){ ll low = dif&(-dif); int cnt = mp[low]; ans[cnt][j] = i; dif -= low; } } } for(int i=0;i<q;++i){ int mi,si; scanf("%d%d",&mi,&si); if(ans[mi][si]==-1) puts("No solution!"); else { int idx = ans[mi][si]; printf("%d",idx); mi -= a[idx]; si -= b[idx]; while(mi){ int idx = ans[mi][si]; printf(" %d",idx); mi -= a[idx]; si -= b[idx]; } puts(""); } } } return 0;}
ZOJ 3812 We Need Medicine（dp、背包、状态压缩、路径记录）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。