(深搜)Sum It Up -- poj --1564

时间:2022-10-01 19:56:09

链接:

http://poj.org/problem?id=1564

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=88230#problem/F

给了一个数 m,给一个由 n 个数组成的数组 a[] , 求和为 m 的 a[] 的子集

(深搜)Sum It Up -- poj --1564

pos 代表的是搜到第 pos 个元素,ans 代表的是 b[] 数组中存的第 ans 个数

我一定要学会深搜!!!

代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n, m, flag;
int a[], b[]; int cmp(int a, int b)
{
return a > b;
}
 ///pos 代表的是搜到第 pos 个元素,
///ans 代表的是 b[] 数组中存的第 ans 个数, b[] 数组里存的是和为 sum 的 void dfs(int pos , int ans, int sum)
{
if(sum == n)
{
flag = ;
sort(b, b + ans, cmp);
for(int i = ; i < ans; ++i)
{
if(!i)
printf("%d",b[i]);
else if(i)
printf("+%d",b[i]);
}
printf("\n");
return;
}
for(int i = pos; i < m; ++i)
{
if(sum + a[i] <= n)
{
b[ans] = a[i];
dfs(i + , ans + , sum + a[i]);
while(i + < m && a[i] == a[i + ])//去重
++i;
}
}
} /*去重:
例如:3 3 2 1 1
为了防止出现 2+1
2+1
这样的重复数据 刚看时我连去重的意思都弄错了,不知道是什么意思,还好调试了一遍知道了
*/
int main ()
{
while(scanf("%d%d", &n, &m), n || m)
{
for(int i = ; i < m; ++i)
scanf("%d", &a[i]);
flag = ;
sort(a, a + m, cmp);
printf("Sums of %d:\n", n);
dfs(, , );
if(!flag)
printf("NONE\n");
}
return ;
}

(深搜)Sum It Up -- poj --1564的更多相关文章

  1. (深搜)棋盘问题 -- poj -- 1321

    链接: http://poj.org/problem?id=1321 Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 2889 ...

  2. Sum It Up POJ 1564 HDU 杭电1258【DFS】

    Problem Description Given a specified total t and a list of n integers, find all distinct sums using ...

  3. 简单深搜:POJ1546——Sum it up

    结束了三分搜索的旅程 我开始迈入深搜的大坑.. 首先是一道比较基础的深搜题目(还是很难理解好么) POJ 1564 SUM IT UP 大体上的思路无非是通过深搜来进行穷举.匹配 为了能更好地理解深搜 ...

  4. poj 3249 Test for Job &lpar;记忆化深搜&rpar;

    http://poj.org/problem?id=3249 Test for Job Time Limit: 5000MS   Memory Limit: 65536K Total Submissi ...

  5. 深搜&plus;回溯 POJ 2676 Sudoku

    POJ 2676 Sudoku Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 17627   Accepted: 8538 ...

  6. POJ 2386 Lake Counting (简单深搜)

    Description Due to recent rains, water has pooled in various places in Farmer John's field, which is ...

  7. USACO 2&period;3&period;3 Zero Sum 和为零(深搜枚举)

    Description 请考虑一个由1到N(N=3, 4, 5 ... 9)的数字组成的递增数列:1 2 3 ... N. 现在请在数列中插入“+”表示加,或者“-”表示减,抑或是“ ”表示空白,来将 ...

  8. poj 2386&colon;Lake Counting(简单DFS深搜)

    Lake Counting Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 18201   Accepted: 9192 De ...

  9. 广搜,深搜,单源最短路径,POJ&lpar;1130&rpar;,ZOJ&lpar;1085&rpar;

    题目链接: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=85 http://poj.org/problem?id=1130 这 ...

随机推荐

  1. Contents Of My Blogs

    C++ How To Use Goto? Preprocessing Directive std::array std::deque std::forward_list std::map std::m ...

  2. 第五章 HID设备

    5.1 HID介绍 为简化USB设备的开发过程,USB提出了设备类的概念.所有设备类都必须支持标准USB描述符和标准USB设备请求.如果有必要,设备类还可以自行定义其专用的描述符和设备请求,这分别被称 ...

  3. 屌丝技能--转Json&lpar;Newtonsoft&period;Json&period;dll&rpar;

    妈妈再也不用为我转Json而担忧了!! 很简单,没什么好说明的,嗯! public class ShowTablePage<T> where T : class, new() { publ ...

  4. java之Spring实现控制反转

    先来复习一下多态吧,简单点讲,就是一个类的引用可以指向其本身以及其子类的对象. Like these: FatherClass a = new FatherClass(); FatherClass a ...

  5. windows安装elasticsearch

    1. 去官网 https://www.elastic.co/cn/ 下载 注意: ES对JDK版本有较高的要求,5.x及以上版本需要JDK8支持,本人此次使用2.4.6版本2. 下载后,JDK先安装, ...

  6. P4715 「英语」Z 语言

    题解: 平衡树维护hash值 为了支持加入删除操作 x*base^y 其中y为他是第k大 同一般的维护方法,我们不用对每个节点维护他的hash值 而是只用记录他的x值(他的位置) 然后通过updata ...

  7. 线段树合并 &vert;&vert; 树状数组 &vert;&vert; 离散化 &vert;&vert; BZOJ 4756&colon; &lbrack;Usaco2017 Jan&rsqb;Promotion Counting &vert;&vert; Luogu P3605 &lbrack;USACO17JAN&rsqb;Promotion Counting晋升者计数

    题面:P3605 [USACO17JAN]Promotion Counting晋升者计数 题解:这是一道万能题,树状数组 || 主席树 || 线段树合并 || 莫队套分块 || 线段树 都可以写..记 ...

  8. Fail2ban 配置

    本例为wordpress管理员登陆限制安装rpm -Uvh http://download.fedoraproject.org/pub/epel/6/x86_64/epel-release-6-8.n ...

  9. 常用关于Android活动的实践技巧

    //知晓当前是在哪一个活动 /* 新建一个BaseActivity类(Java class), 继承自AppCompatActivity * 重写 onCreate()方法,已有的活动无需再继承自Ap ...

  10. 【MYSQL】语法复习

    一.数据类型 截图来源: http://www.runoob.com/mysql/mysql-data-types.html 二.基本语句 1.创建数据表 -- 主键自增,T_User CREATE ...