K - 背包

Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

Submit Status

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
 
 
这道题可以使用DP做,dp(i)代表i这个数字是否可称,dp(i)=(( dp(j)==1 && 1<j<sum )     j==i + || - 新加入的数字 ?)
 
#include"iostream"
#include"algorithm"
#include"cstring"
using namespace std; const int maxn=; int dp[maxn],ok[maxn],ans[maxn]; int main()
{
int sum,n,temp; while(cin>>n)
{
memset(dp,,sizeof(dp));
dp[]=;
sum=;
for(int i=;i<=n;i++)
{
cin>>temp;
memset(ok,,sizeof(ok));
sum+=temp;
for(int j=;j<=sum;j++) if(dp[j])
{
ok[j+temp]=;
ok[abs(j-temp)]=;
}
for(int j=;j<=sum;j++) if(ok[j])
dp[j]=;
}
int top=;
for(int i=;i<=sum;i++)
{
if(dp[i]==) ans[top++]=i;
}
cout<<top<<endl;
if(top)
{
for(int j=;j<top-;j++) cout<<ans[j]<<" ";
cout<<ans[top-]<<endl;
}
}
return ;
}

你好

最新文章

  1. prefix pct文件配置Xcode
  2. easyui-datagrid连接数据库实现分页查询数据
  3. javascript选择器querySelector和querySelectorAll的使用和区别
  4. WampServer64提示You don&#39;t have permission to access
  5. 从零开始搭建Docker Swarm集群
  6. Reinforcement Learning
  7. js日期相关函数总结分享
  8. eclipse中英文切换--四种方式
  9. node.js 模块和包
  10. (转载)linux那点事儿(上)
  11. 关于WEB三层架构的思考
  12. 史上最全的FTP网址
  13. JavaScript 原型中的哲学思想
  14. Java8内置的函数式接口
  15. Android插件化的兼容性(下):突破Android P中灰黑名单的限制
  16. 【Java每日一题】20170210
  17. [leetcode]36. Valid Sudoku验证数独
  18. ss is one another utility to investigate sockets(特适合大规模tcp链接)
  19. java string截取两个字符串之间的值
  20. Kafka 之 入门

热门文章

  1. Step 4: Install and Configure Databases
  2. IOS - PDF合并 - 转
  3. 455 Assign Cookies 分发饼干
  4. IIS中不让下级应用程序继承主域名的web.config配置
  5. iOS捷径(Workflow 2.0)拓展
  6. 微软2017年预科生计划在线编程笔试 A Legendary Items
  7. ViewPager讲解以及ViewFlipper
  8. Python3.0 调用HTMLTestRunner生成的报告中不能显示用例中print函数的输出
  9. STL中unique的使用
  10. MFC中调用Windows API函数的方式