poj 1564 Sum It Up
题目连接
http://poj.org/problem?id=1564
Sum It Up
Description
Given a specified total t and a list of n integers, find all distinct sums using numbers from the list that add up to t. For example, if t = 4, n = 6, and the list is [4, 3, 2, 2, 1, 1], then there are four different sums that equal 4: 4, 3+1, 2+2, and 2+1+1. (A number can be used within a sum as many times as it appears in the list, and a single number counts as a sum.) Your job is to solve this problem in general.
Input
The input will contain one or more test cases, one per line. Each test case contains t, the total, followed by n, the number of integers in the list, followed by n integers x 1 , . . . , x n . If n = 0 it signals the end of the input; otherwise, t will be a positive integer less than 1000, n will be an integer between 1 and 12 (inclusive), and x 1 , . . . , x n will be positive integers less than 100. All numbers will be separated by exactly one space. The numbers in each list appear in nonincreasing order, and there may be repetitions.
Output
For each test case, first output a line containing `Sums of', the total, and a colon. Then output each sum, one per line; if there are no sums, output the line `NONE'. The numbers within each sum must appear in nonincreasing order. A number may be repeated in the sum as many times as it was repeated in the original list. The sums themselves must be sorted in decreasing order based on the numbers appearing in the sum. In other words, the sums must be sorted by their first number; sums with the same first number must be sorted by their second number; sums with the same first two numbers must be sorted by their third number; and so on. Within each test case, all sums must be distinct; the same sum cannot appear twice.
Sample Input
4 6 4 3 2 2 1 1
5 3 2 1 1
400 12 50 50 50 50 50 50 25 25 25 25 25 25
0 0
Sample Output
Sums of 4:
4
3+1
2+2
2+1+1
Sums of 5:
NONE
Sums of 400:
50+50+50+50+50+50+25+25+25+25
50+50+50+50+50+25+25+25+25+25+25
dfs。。
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<set>
using std::set;
using std::sort;
using std::pair;
using std::swap;
using std::queue;
using std::multiset;
#define pb(e) push_back(e)
#define sz(c) (int)(c).size()
#define mp(a, b) make_pair(a, b)
#define all(c) (c).begin(), (c).end()
#define iter(c) decltype((c).begin())
#define cls(arr, val) memset(arr, val, sizeof(arr))
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define tr(c, i) for(iter(c) i = (c).begin(); i != (c).end(); ++i)
const int N = 1010;
const int INF = 0x3f3f3f3f;
typedef unsigned long long ull;
bool f;
int n, tot, tar, A[N], B[N];
void dfs(int cur, int ret, int k) {
if (ret == tar) {
f = true;
for (int i = 0; i < k; i++) {
if (!i) printf("%d", B[i]);
else printf("+%d", B[i]);
}
putchar('\n');
return;
}
for (int i = cur; i < n; i++) {
if (i == cur || A[i] != A[i - 1]) { // 判重
B[k] = A[i];
dfs(i + 1, ret + A[i], k + 1);
}
}
}
int main() {
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w+", stdout);
#endif
while (~scanf("%d %d", &tar, &n), n) {
f = false;
rep(i, n) scanf("%d", &A[i]);
printf("Sums of %d:\n", tar);
dfs(0, 0, 0);
if (!f) { puts("NONE"); continue; }
}
return 0;
}
最新文章
- WPF根据Oracle数据库的表,生成CS文件小工具
- python学习之day5,装饰器,生成器,迭代器,json,pickle
- iptables的conntrack表满了导致访问网站很慢
- [Java Web]Error parsing HTTP request header Note: further occurrences of HTTP header parsing errors
- Postgresql存储过程调试:PostgreSQL 之 Function NOTICE
- The &#39;Microsoft.ACE.OLEDB.12.0&#39; provider is not registered on the local machine
- Flexigrid在IE下不显示数据的处理
- LOGSTASH再入门第一发
- Asp_CRUD
- [Unit Testing] Directive testing, require parent controller
- jQuery Lint: enables you to automatically inject jQuery Lint into the page as it is loaded (great for ad-hoc code validation)
- iOS 多线程NSThread理解与场景示例
- eclipse+HBASE开发环境搭建(已实践)
- 了解 HTTPS,读这篇文章就够了
- OOP AOP
- keil5到iar8的使用配置迁移
- Hadoop项目实战-用户行为分析之应用概述(二)
- 转载 Spring、Spring MVC、MyBatis整合文件配置详解
- Fake NP CodeForces - 805A (思维)
- The Shortest Statement CodeForces - 1051F(待测试)