集训第五周 动态规划 K题 背包
2024-08-25 16:31:52
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 ;
}
你好
最新文章
- prefix pct文件配置Xcode
- easyui-datagrid连接数据库实现分页查询数据
- javascript选择器querySelector和querySelectorAll的使用和区别
- WampServer64提示You don&#39;t have permission to access
- 从零开始搭建Docker Swarm集群
- Reinforcement Learning
- js日期相关函数总结分享
- eclipse中英文切换--四种方式
- node.js 模块和包
- (转载)linux那点事儿(上)
- 关于WEB三层架构的思考
- 史上最全的FTP网址
- JavaScript 原型中的哲学思想
- Java8内置的函数式接口
- Android插件化的兼容性(下):突破Android P中灰黑名单的限制
- 【Java每日一题】20170210
- [leetcode]36. Valid Sudoku验证数独
- ss is one another utility to investigate sockets(特适合大规模tcp链接)
- java string截取两个字符串之间的值
- Kafka 之 入门
热门文章
- Step 4: Install and Configure Databases
- IOS - PDF合并 - 转
- 455 Assign Cookies 分发饼干
- IIS中不让下级应用程序继承主域名的web.config配置
- iOS捷径(Workflow 2.0)拓展
- 微软2017年预科生计划在线编程笔试 A Legendary Items
- ViewPager讲解以及ViewFlipper
- Python3.0 调用HTMLTestRunner生成的报告中不能显示用例中print函数的输出
- STL中unique的使用
- MFC中调用Windows API函数的方式