题目描述
给你n根火柴棍，你可以拼出多少个形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整数（若该数非零，则最高位不能是0）。用火柴棍拼数字0-9的拼法如图所示：
注意：
- 加号与等号各自需要两根火柴棍
- 如果A≠B，则A+B=C与B+A=C视为不同的等式(A,B,C>=0)
- n根火柴棍必须全部用上
输入格式
一个整数n(n<=24)。
输出格式
一个整数，能拼成的不同等式的数目。
输入输出样例
输入 #1
14
输出 #1
2
输入 #2
18
输出 #2
9
我的分析
刚开始做这道题的时候，因为题目标签“搜索”蛊惑，我就真的一根脑经琢磨着用DFS做，后来证明这个做法并不是明智之举。
当时我先定义了一个数组，表示各个数与对应火柴数目的映射关系。因为不确定各个数具体范围是多少，为了保险起见，我的数组大小定义为1001，0-1000下标对应的元素即组成这些数的火柴数目。然后采取DFS的手段枚举所有情况，找出符合条件的所有三个数的组合。
－－然而悲催的是，最后Time Limit Exceed!!／（ㄒｏㄒ）／～～
我痛定思痛，冷静分析了一波，应该是堆栈调用过多(3层)，每次调用又经历一个1000的for循环，电脑遭不住了。(当时想的是3个数嘛，搜索3次嘛，后来才知道这个想法多么愚蠢，因为确定了前两个数，第三个数就是他们的和，自然确定了啊，根本不需要再搜索了，只需要调用两次即可／（ㄒｏㄒ）／～～)
正当我心灰意冷，准备放弃时，我耳边突然想起了OI界的神之诫言：“骗分过样例，暴力出奇迹”
于是，我删掉之前的代码，准备用暴力法卷头重来！！(好吧，这应该是贬义词)
我在对之前的不堪入目的算法作出了如下改进，首先我没有再申请了1001大小的数组，而是用一个函数即时计算每一个数对应的火柴数，而这仅仅需要大小为10的数组(用于表示出0-9对应的火柴数)，其余数对应的火柴数皆可用函数在此基础上计算出。我把DFS的递归也也换成了双重for循环的暴力迭代，最终代码如下：
#include<iostream>
using namespace std;
//对应0-9的火柴数
int map[10]={6,2,5,5,4,5,6,3,7,6};
//计算某个数对应的火柴数
int match(int n){
//0单独处理
if(n==0) return 6;
int count=0;
//分离该数各位数分别计算火柴数
//然后将火柴数累加
while(n){
count +=map[n%10];
n/=10;
}
return count;
}
int main(){
int n;
cin>>n;
int count=0;
for(int i=0;i<=1000;++i){
for(int j=0;j<=1000;++j){
//因为+,=共占４根火柴，故-4
if(match(i)+match(j)+match(i+j)==n-4)
count++;
}
}
cout<<count<<endl;
return 0;
}
最后，如愿以偿的AC啦！
