博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
搜索专题: HDU1258Sum It Up
阅读量:5824 次
发布时间:2019-06-18

本文共 3362 字,大约阅读时间需要 11 分钟。

Sum It Up

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6720    Accepted Submission(s): 3535
Problem 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 x1,...,xn. 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 x1,...,xn 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 distince; the same sum connot 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
 
Source
Problem :     Judge Status : Accepted
RunId : 21150701    Language : G++    Author :
Code Render Status : Rendered By HDOJ G++ Code Render Version 0.01 Beta
#include<iostream> #include<cstdio> #include<cstring> #include<set> #include<algorithm> using namespace std; const int N = 50+5; int x,n,a[N],save[N],pos; bool flag; bool cmp(const int x,const int y){ return x>y; } void DFS(int sum,int d){ if(sum>x) return; if(sum==x){ flag = false; for(int i=0;i<pos-1;i++) printf("%d+",save[i]); printf("%d\n",save[pos-1]); return ; } int last = -1; for(int i=d+1;i<=n;i++){ if(a[i]!=last){ save[pos++] = a[i]; last = a[i]; DFS(sum+a[i],i); pos--; } } } int main(){ while(scanf("%d %d",&x,&n)==2 &&(x||n)){ for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+n+1,cmp); flag = true; printf("Sums of %d:\n",x); DFS(0,0); if(flag) printf("NONE\n"); } }
#include
#include
#include
#include
#include
using namespace std;const int N = 50+5;int x,n,a[N],save[N],pos;bool flag;bool cmp(const int x,const int y){
return x>y;}void DFS(int sum,int d){
if(sum>x) return; if(sum==x){
flag = false; for(int i=0;i

转载于:https://www.cnblogs.com/Pretty9/p/7347699.html

你可能感兴趣的文章
ActivityManager: Warning: Activity not started, its current task has been brought to the front
查看>>
GopherChina 2018
查看>>
基于C API的SQLite3基本数据库操作
查看>>
使用 SailingEase WinForm 框架构建复合式应用程序(插件式应用程序)
查看>>
解析xlsx文件---Java读取Excel2007
查看>>
使用ssh向sqlserver2005数据库中保存image类型的二进制图片
查看>>
淘宝JAVA中间件Diamond详解(二)---原理介绍
查看>>
Gatling的进阶三
查看>>
工信部征集2019年大数据优秀产品和应用解决方案
查看>>
为什么很少见工资高的程序员炫富?
查看>>
阿里B2B总裁戴珊:全球化的天猫双11,普惠全球共享快乐
查看>>
ofo用科技引领行业进入4.0时代 用户粘性连续8个月远甩摩拜
查看>>
无法拒绝|华为618最高优惠1000元 更有梅西签名球衣奉送
查看>>
乐信Q2季报图解:调整后净利过5亿 同比增长776%
查看>>
兰州青年志愿者“中西合璧”玩快闪 温暖旅客回家路
查看>>
计划10年建10万廉价屋 新西兰政府:比想象中难
查看>>
甘肃发首版《3D打印职业教育教材》:校企合作育专才
查看>>
内蒙古2019年精准脱贫新“目标”:20个贫困旗县全部摘帽
查看>>
韩国国会议员涉嫌投机炒房 检方称已立案调查
查看>>
李娜入选国际网球名人堂 成亚洲第一人
查看>>