我写了一个程序来解决ACM的这个问题。
火柴棒是表示数字的理想工具。用火柴棒表示十个十进制数字的常见方法如下：
这与普通闹钟上显示数字的方式完全相同。有了一定数量的火柴棒，您可以生成各种数字。我们想知道使用所有火柴棒可以创建的最小和最大数字是什么。
输入
第一行为正整数：测试用例数，最多100个。之后每个测试用例：
一行包含一个整数n（2≤n≤100）：您拥有的火柴棒数量。
输出
每个测试用例：
一行，由一个空格分隔的最小和最大数字。两个数字都应该是正数且不包含前导零。
样例输入
4 3 6 7 15 样例输出
7 7 6 111 8 711 108 7111111
问题在于对于100根火柴棒来说，暴力搜索的搜索树太大了，速度太慢。
以下是前10个数字的结果：
2: 1 1
3: 7 7
4: 4 11
5: 2 71
6: 6 111
7: 8 711
8: 10 1111
9: 18 7111
10: 22 11111
最大值的模式很容易，但我没有看到最小值的快捷方式。有人能提出更好的解决方法吗？这是我使用的代码：
#include <iostream>
#include <string>
using namespace std;
#define MAX 20 //should be 100
//match[i] contains number of matches needed to form i
int match[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
string mi[MAX+1], ma[MAX+1];
char curr[MAX+1] = "";
//compare numbers saved as strings
int mycmp(string s1, string s2)
{
int n = (int)s1.length();
int m = (int)s2.length();
if (n != m)
return n - m;
else
return s1.compare(s2);
}
//i is the current digit, used are the number of matchsticks so far
void fill(int i, int used)
{
//check for smaller and bigger values
if (mycmp(curr, mi[used]) < 0) mi[used] = curr;
if (mycmp(curr, ma[used]) > 0) ma[used] = curr;
//recurse further, don't start numbers with a zero
for (int a = i ? '0' : '1'; a <= '9'; a++) {
int next = used + match[a-'0'];
if (next <= MAX) {
curr[i] = a;
curr[i+1] = '\0';
fill(i + 1, next);
}
}
}
int main()
{
//initialise
for (int i = 0; i <= MAX; i++) {
mi[i] = string(MAX, '9');
ma[i] = "0";
}
//precalculate the values
fill(0, 0);
int n;
cin >> n;
//print those that were asked
while (n--) {
int num;
cin >> num;
cout << mi[num] << " " << ma[num] << endl;
}
return 0;
}
编辑：最终我使用了动态规划的解决方案。之前我尝试过使用dp，但是我在操作二维状态数组时搞砸了。这里提供的解决方案要好得多。谢谢！