zoj 3812 状压dp
转载:http://blog.csdn.net/qian99/article/details/39138329
题意:给出n个物品,每个物品有两种属性Wi,Ti,有q组查询,每组查询要求在n个物品中选出一些,并使得两个属性的和为Mi,Si。
思路:刚开始看感觉是神题,后来仔细想了想,其实本质上就是个背包。最裸着写的话,那么就是dp[i][j][k]表示使用前i个物品,是否可以凑出第一个属性j,第二个属性k,要输出方案的话记录一下路径就可以了。一开始这么写了一发,加了一些乱七八糟的优化,还是会T。虽然这题时限还算宽,但这么写复杂度还是太高了。考虑到第一个属性最多只有50,那么可以用一个二进制数来表示是否能凑出第一个属性的情况,即:第i位为1表示可以凑出i。使用这种方法的好处是对于物品i可以直接算出第一种属性的组合情况,枚举一下新增的位,更新一下结果就行了。
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<cmath>
#include<vector>
#define inf 0x3f3f3f3f
#define Inf 0x3FFFFFFFFFFFFFFFLL
#define eps 1e-8
#define pi acos(-1.0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 400 + 10;
const int M = 51;
short ans[200010][52];
ull f[200010];
int W[maxn],T[maxn];
map<ull,int>mp;
int main()
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
for(int i = 1;i <= M + 1;++i)
mp[1LL<<(i-1LL)] = i;
int t,n,q;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&q);
memset(ans,0,sizeof(ans));
memset(f,0,sizeof(f));
f[0] = 1;
ull v,x;
for(int i = 1;i <= n;++i)
{
scanf("%d%d",&W[i],&T[i]);
for(int j = 200000;j >= T[i];--j)
{
v = f[j]; //f[j]表示第二个属性为j时,能够凑出的第一个属性的集合,用一个二进制数表示,第i位为1表示可以凑出这个数
f[j] |= (f[j - T[i]]<<W[i]) & ((1LL<<M+1) - 1); //计算使用当前物品能够得到的新的集合,在集合f[j - T[i]]添加W[i]的物品,
//即原来能得到的每个值加上W[i],等价于将其左移W[i]位
for(ull k = v ^ f[j];k ; k &= k-1) //枚举新增加的集合
{
x = (k ^ (k - 1)) & k;
ans[j][mp[x] - 1] = i; //将新增的位置更新,记录是使用了哪个物品达到的这个状态
}
}
}
int m,s,p;
for(int i = 0;i < q;++i)
{
scanf("%d%d",&m,&s);
if(!ans[s][m])
puts("No solution!");
else
{
printf("%d",ans[s][m]);
p = ans[s][m];
m -= W[p];
s -= T[p];
while(m)
{
p = ans[s][m];
printf(" %d",p);
m -= W[p];
s -= T[p];
}
puts("");
}
}
}
return 0;
}
最新文章
- 1-web应用之LAMP源码环境搭建
- 【C++】输入多行数字到数组
- JSTL的if-else表式
- Java中synchronized详解
- Noip2015总结
- JS中NULL和undifined区别及NULL的作用
- JDBC自动提交和批处理操作
- access 语句错误
- Cookie和Session (转)
- python—异常
- 查看oracle表空间
- PhantomJS在Selenium中被标记为过时的应对措施
- Windows has encountered a critical problem and will restart automatically in one minute. Please save your work now
- 《DSP using MATLAB》Problem 7.1
- mysql 多个and的简写
- mysql 中find_in_set()和in()用法比较
- 2018.07.17 CQOI2017 余数求和(整除分块)
- 使用 Project Siena 生成一个 Windows Store 应用
- 分享一个查找linux命令的网站
- WebAssembly 介绍