`

HDU 1258 Sum It Up

阅读更多
http://acm.hdu.edu.cn/showproblem.php?pid=1258

题意:给你一个数t作为最后等式的和,再给你n个数作为等式的加数,每个加数最多只能使用一次,要求输出所有满足条件(加数从大到小输出)的等式,并且不能重复

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


#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
//#include <ctime>
#include <ctype.h>
using namespace std;
#define LL __int64
#define inf 0x7fffffff
#define M 15

map<string, int> m;
int num[M], ans, n;
bool vis[M], flag;
char res[105];

void dfs (int x, int sum, int k)
{
	int i;
	if (sum == ans)
	{
		res[k] = 0;		//+结束符,然后判是否重复
		if (m[res] == 0)
		{
			flag = true;
			m[res] = 1;
			printf ("%d", (int)res[0]);	//转换成整数输出
			for (i = 1; i < k; i++)
				printf ("+%d", (int)res[i]);
			printf ("\n");
		}
		return ;
	}
	for (i = x + 1; i < n; i++)		//由于是递增,所以从x+1开始
	{
		if (vis[i] || sum + num[i] > ans)
			continue;
		vis[i] = true;
		res[k] = num[i];
		dfs (i, sum+num[i], k+1);
		vis[i] = false;
	}
}

int main()
{
	int i;
	while (scanf ("%d%d", &ans, &n), (ans||n))
	{
		printf ("Sums of %d:\n", ans);
		m.clear();
		for (i = 0; i < n; i++)
			scanf ("%d", num+i);
		flag = false;
		for (i = 0; i < n; i++)
		{
			res[0] = num[i];	//直接当num[i]是ASCⅡ码使用,方便map记录重复
			memset (vis, false, sizeof(vis));
			vis[i] = true;
			dfs (i, num[i], 1);
		}
		if (!flag)
			puts ("NONE");
	}
    return 0;
}
2
0
分享到:
评论

相关推荐

    hdu1297.rar_SUM_hdu1297

    杭电acm1297 #include&lt;stdio.h&gt; #include&lt;string.h&gt; #define m 1002 int f[m][70]={{1,1},{1,1},{1,2},{1,4}} void add(int p[],int q[],int sum[]) ...=10000){sum[i]-=10000 sum[i+1]++ } }

    hdu.rar_hdu

    HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...

    HDU_2010.rar_hdu 2010_hdu 20_hdu acm20

    【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...

    HDU题目java实现

    【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...

    ACM HDU题目分类

    ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...

    hdu1250高精度加法

    ### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...

    HDU1059的代码

    HDU1059的代码

    HDU DP动态规划

    【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...

    hdu1001解题报告

    hdu1001解题报告

    hdu 1574 passed sorce

    hdu 1574 passed sorce

    hdu动态规划算法集锦

    根据提供的信息,我们可以总结出以下关于“hdu动态规划算法集锦”的知识点: ### 动态规划基础概念 动态规划是一种解决多阶段决策问题的方法,它通过将原问题分解为互相重叠的子问题,利用子问题的解来构建原问题...

    ACM HDU

    【ACM HDU】指的是在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)中,参赛者在杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的在线评测系统上完成并已解决的题目集合...

    hdu2101解决方案

    hdu2101AC代码

    hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj

    【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...

    解题代码 hdu1241

    根据给定的文件信息,我们可以得知这是一段用于解决HDU(Hdu Online Judge)编号为1241的问题的代码。该代码主要采用了深度优先搜索(DFS)算法来解决问题。 #### 二、DFS(Depth First Search)算法原理 **定义:...

    杭电ACMhdu1163

    【标题】:杭电ACMhdu1163 【描述】:这是一道源自杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的ACM编程竞赛题目,编号为1163。这类问题通常需要参赛者利用计算机编程解决数学、逻辑或算法上的挑战,...

    hdu 5007 Post Robot

    hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。

    hdu acm1166线段树

    hdu 1166线段树代码

Global site tag (gtag.js) - Google Analytics