[POJ1014]Dividing(二进制优化多重背包)
2024-09-30 20:32:17
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std; int T,A[10];
bool f[100010]; inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
} int main(){
for(;;){
int s=0,fg=0;
for(int i=1;i<=6;++i)A[i]=read(),s+=A[i]*i;
if(!s)break;
printf("Collection #%d:\n",++T);
if(s&1^1){//原来打成s^1&1WA了233
s>>=1,memset(f,0,sizeof(f)),f[0]=1;
for(int i=1;i<=6;++i){
for(int j=1;j<=A[i];j*=2){
for(int k=s;k>=j*i;--k)if(f[k-j*i])f[k]=1;
A[i]-=j;
}
if(A[i])for(int k=s;k>=A[i]*i;--k)if(f[k-A[i]*i])f[k]=1;
}
if(f[s])fg=1;
}
if(fg)printf("Can be divided.\n\n");else printf("Can't be divided.\n\n");
}
return 0;
}
最新文章
- C++的内存泄漏检测
- Java性能调优
- Maven进价:Maven的生命周期阶段
- 树莓派3 Windows 10 IoT Core
- SQL Server 2012:SQL Server体系结构——一个查询的生命周期(第2部分)
- 使用ar命令删除iOS静态库重复编译的.o文件
- QQ分组实现,可收缩---ExpandableListView
- ubuntu下修改时区
- (转载) ExtJs大比拼JQuery:Dom文档操作
- php 二维数组以树形输出(转)
- Eric Pement的单行awk命令收集
- python高级编程之超类02:super的缺陷
- Mac终端查看sqlite3数据库、表数据等
- CentOS 7.2 Ubuntu 18部署Rsync + Lsyncd服务实现文件实时同步/备份
- MongoDB3.6 一键化自动部署方案
- docker+ubuntu14.04+cuda7.0
- springboot中使用mybatis显示执行sql
- RocketMQ集群部署记录
- linux中断源码分析 - 概述(一)
- 自学Linux Shell17.1-正则表达式