砝码称重

题面

题目描述 5 个砝码，用天平称重时，我们希望用尽可能少的砝码组合称出尽可能多的重量。如果只有 5 个砝码，重量分别是 1，3，9，27，81。则它们可以组合称出 1 到 121 之间任意整数重量（砝码允许放在左右两个盘中）。本题目要求编程实现：对用户给定的重量，给出砝码组合方案。

输入

19

输出

27-9+1

ac代码

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#include<map>

const int N = 100;

using namespace std;

int ans = 0x3f3f3f3f;
int n;
int a[6] = {1,3,9,27,81};
int bb[6], cc[6];
char b[6], c[6];

void dfs(int sum, int cnt, int pos)
{
	if (cnt >= ans)return;
	
	if (pos < -1)return;

	if (sum == n)
	{
		for (int i = 0; i < 5; i++)
		{
			cc[i] = bb[i];
			c[i] = b[i];
		}
		ans = cnt;
		return ;
	}

	dfs(sum, cnt, pos - 1);


	bb[pos] = a[pos];
	b[pos] = '+';
	dfs(sum + a[pos], cnt + 1, pos - 1);
	bb[pos] = 0;
	b[pos] = ' ';


	bb[pos] = a[pos];
	b[pos] = '-';
	dfs(sum - a[pos], cnt + 1, pos - 1);
	bb[pos] = 0;
	b[pos] = ' ';
}

int main()
{
	cin >> n;

	dfs(0, 0, 4);
	


	int m = 0;

	for (int i = 4; i >= 0; i--)
	{
		if (cc[i]) {
			if (m)cout << c[i];
			cout << cc[i]; m++;
		}
	}
	
	return 0;
}