Lightoj 1127 - Funny Knapsack 【二分】
2024-08-31 17:51:26
题目链接: problem=1127">http://www.lightoj.com/volume_showproblem.php?problem=1127
题意:有n个物体(n<30)和一个容量为W的容器。问将容器不装满的放置物品的方式有多少种。
思路 : 状态压缩+二分。将前n/2个物体看做一个总体,将剩下的看做一个总体。1<<(n/2)个状态代表前一半的物品使用情况,然后求出每一种状态的总的体积。排序。对于后面的那一半也是。答案仅仅需枚举一半然后在还有一半中找和W差的下界就可以。
代码:
#include <stdio.h>
#include <ctime>
#include <math.h>
#include <limits.h>
#include <complex>
#include <string>
#include <functional>
#include <iterator>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <bitset>
#include <sstream>
#include <iomanip>
#include <fstream>
#include <iostream>
#include <ctime>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <time.h>
#include <ctype.h>
#include <string.h>
#include <assert.h>
using namespace std;
int n;
long long w;
long long a[1000000];
long long s1[1000000];
long long s2[1000000];
int main()
{
int t;
scanf("%d", &t);
int cases = 1;
while (t--)
{
memset(s1, 0, sizeof(s1));
memset(s2, 0, sizeof(s2));
memset(a, 0, sizeof(a));
scanf("%d %lld", &n, &w);
for (int i = 0; i < n; i++)
scanf("%lld", &a[i]);
int t1 = n >> 1;
int t2 = n - t1;
int r1 = 1 << t1;
int r2 = 1 << t2;
for (int i = 0; i < r1; i++)
for (int j = 0; j < t1; j++)
{
if (i &(1 << j))
s1[i] += a[j];
}
for (int i = 0; i < r2; i++)
for (int j = 0; j < t2; j++)
{
if (i &(1 << j))
s2[i] += a[t1 + j];
}
sort(s2, s2 + r2 );
long long ans = 0;
for (int i = 0; i < r1; i++)
{
if (w - s1[i] >= 0)
ans += upper_bound(s2, s2 + r2, w - s1[i]) - s2;
}
printf("Case %d: %lld\n", cases++, ans);
}
return 0;
}
最新文章
- HTTPS 双向认证构建移动设备安全体系
- linux驱动开发之块设备学习笔记
- Calendar获取星期
- oracle查询表的索引
- origin 8.5 曲线拟合,延长曲线范围
- maxscript,MAXScript Listener下输入print ";hi";为什么输出两次
- Javascript操纵Cookie--转
- matlab search path
- Hbase 建表基本命令总结
- 学习使用crosswalk
- 可能性dp+减少国家HDU4336
- coco2d-x CCScrollView实现背包翻页,仅供参考
- Python系列教程大汇总
- Android高斯模糊技术,实现毛玻璃效果(转)
- 【DDD】领域驱动设计实践 —— UI层实现
- cs231n spring 2017 lecture8 Deep Learning Networks 听课笔记
- NIO-学习
- IDEA中运行DirectKafkaWordCount程序
- Problem 1: Multiples of 3 and 5
- django项目的部署
热门文章
- lsof---查看你进程开打的文件
- 用Google Chrome 浏览器打开Unity打包的WebGL
- 05-数据类型转换(bool转换)
- 【转】DotNet加密方式解析--非对称加密
- 一款很不错的html转xml工具-Html Agility Pack 实现html转Xml
- Using a Plugin
- ajax --- 解决ajax跨域请求导致session失效的问题
- HTTP 各种特性应用(二)
- 玲珑杯 Round #18 A -- 计算几何你瞎暴力
- VirtualBox内刚刚安装完CentOS6.9和7系统,无法调整屏幕的分辨率,也无法设置共享文件夹。解决的方法就是安装VirtualBox客户端增强包。