The Balance

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 135 Accepted Submission(s): 88
 
Problem Description
Now you are asked to measure a dose of medicine with a balance and a number of weights. Certainly it is not always achievable. So you should find out the qualities which cannot be measured from the range [1,S]. S is the total quality of all the weights.
 
Input
The input consists of multiple test cases, and each case begins with a single positive integer N (1<=N<=100) on a line by itself indicating the number of weights you have. Followed by N integers Ai (1<=i<=N), indicating the quality of each weight where 1<=Ai<=100.
 
Output
            For each input set, you should first print a line specifying the number of qualities which cannot be measured. Then print another line which consists all the irrealizable qualities if the number is not zero.
 
Sample Input
3
1 2 4
3
9 2 1
 
Sample Output
0
2
4 5
 
 
Source
HDU 2007-Spring Programming Contest
 
Recommend
lcy
 
/*
题意:给出n个砝码的质量,让你求出在[1,s]范围内不能组成的质量,s是质量总和,这个题不一样的地方是天平两边都可以放砝码 初步思路:可以看成一个背包问题,每个取或不取,但是这个题有一个新的状态,就是
*/
#include<bits/stdc++.h>
using namespace std;
int v[];
int dp[];//dp[i]表示i金额能组成或不能组成
int vis[];//记录一下能组成的金额
int n;
int s=;
void init(){
memset(vis,,sizeof vis);
memset(dp,,sizeof dp);
s=;
}
int main(){
// freopen("in.txt","r",stdin);
while(scanf("%d",&n)!=EOF){
init();
for(int i=;i<=n;i++){
scanf("%d",&v[i]);
s+=v[i];
}
vis[]=;
for(int i=;i<=n;i++){
memset(dp,,sizeof dp);
for(int j=;j<=s;j++){
if(vis[j]){//j金额能组成
dp[j+v[i]]=;//加上当前金额那么也是可以的
dp[abs(j-v[i])]=;//减去这个金额的也是可以的
}
}
for(int j=;j<=s;j++){
if(dp[j]) vis[j]=;
}
}
int res=;
for(int i=;i<=s;i++)
if(!vis[i])
res++;
printf("%d\n",res);
if(res==) continue;
int f=;
for(int i=;i<=s;i++){
if(!vis[i]){
if(f==){
printf("%d",i);
f=;
}else{
printf(" %d",i);
}
}
}
printf("\n");
}
return ; }

最新文章

  1. 求n!最后一位非零数
  2. UISearchController使用
  3. Python3基础 reverse 将列表倒序排列
  4. sql datetime操作
  5. MVC 登录认证与授权及读取登录错误码
  6. archlinux安装输入法需要的包及archlinux无法使用输入法的解决
  7. cf(#div1 B. Dreamoon and Sets)(数论)
  8. BZOJ2721 [Violet 5]樱花
  9. LeetCode Path Sum II (DFS)
  10. fastjson生成和解析json数据
  11. CSS3几个速记标签2
  12. OC - 14.NSOperation与NSOperationQueue
  13. 解压版本 Tomcat配置--转
  14. Java多线程:CopyOnWrite容器
  15. CRM 员工创建并分配用户
  16. JavaScript动态加载CSS和JS文件
  17. 2016年蓝桥杯省赛A组c++第8题(暴力求解)
  18. bzoj 1093 最大半连通子图 - Tarjan - 拓扑排序 - 动态规划
  19. Intellij 部署项目java.lang.ClassNotFoundException: org.springframework.web.context.ContextLoaderListener
  20. L3-009 长城 (30 分)

热门文章

  1. XML的序列化(Serializer)
  2. servlet生成验证码
  3. 第一次安装jshint,jshint新手使用记录
  4. HDFS概述(6)————用户手册
  5. [bzoj1066] [SCOI2007] 蜥蜴 - 网络流
  6. php中常用的字符串长度函数strlen()与mb_strlen()实例解释
  7. 原生JS封装animate运动框架
  8. Oracle的常用命令之备份和恢复数据库
  9. 关于form表单上传图片的一些记录
  10. 前端魔法堂——异常不仅仅是try/catch