HDU 1258 Sum It Up

http://acm.hdu.edu.cn/showproblem.php?pid=1258
제목:마지막 등식 의 합 으로 숫자 t 를 드 리 고 n 개 수 를 등식 의 덧셈 으로 드 리 겠 습 니 다.모든 덧셈 은 최대 한 번 만 사용 할 수 있 습 니 다.모든 만족 조건(덧셈 은 큰 것 에서 작은 출력)의 등식 을 출력 하 라 고 요구 합 니 다.또한 샘플 입력 을 반복 할 수 없습니다 4 6 4 3 2 1 1 5 3 2 1 400 12 50 50 50 50 25 25 25 25 25 20 0 샘플 출력 합계 4:4 3+1 2+2 2+1 2+1+1 합계 5:NONE 합계 400:50+50+50+50+50+25+25+25+25+25 50+50+50+50+50+25+25+25 50+50+50+25+25+25+25+25+25+25+25+25+25+25+25+25+25+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 ("
"); } 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:
", 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; }

좋은 웹페이지 즐겨찾기