搜索专题: HDU1258Sum It Up
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
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.
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.
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.
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
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
RunId : 21150701 Language : G++ Author : hnustwanghe
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<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");
}
}
最新文章
- matlab画图函数plot()/set/legend
- LINQ系列:LINQ to SQL Where条件
- Ajax Step By Step5
- 一个数如果恰好等于它的因子之和,这个数就称为 ";完数 ";。例如6=1+2+3.编程&#160;&#160;&#160;&#160; 找出1000以内的所有完数。
- Web应用开发工具及语言需要具备的功能探索
- C#创建UTF8无BOM文本文件
- (转)iOS7界面设计规范(1) - UI基础 - 为iOS7而设计
- js单例模式
- mysql 增量导入到elasticsearch
- 【G-BLASTN 1.0正式发布】
- java8之lambda表达式入门
- Mahout安装部署
- 关于aop的两种方式-基于注解和基于aspectj
- 拾人牙慧篇之——linux文件挂载,基于nfs的文件共享系统安装配置
- linux 查看系统资源命令
- js 判断数组中是否有某值
- Stm32串口通信(USART)
- (4.28)for xml path 在合并拆分上的作用演示
- 厉害了,他用PS不是P照片而是……
- 1089. Insert or Merge (25)-判断插入排序还是归并排序