这道题用枚举会超时,请用DFS
by 攀岩高手 @ 2017-05-26 21:14:28
如果用枚举好像也可以,代码如下
```cpp
#include <iostream>
using namespace std;
// 子程序用来计算整数x需要的火柴棍数
int fun(int x)
{
int num = 0; // 计数器
int f[] = {6,2,5,5,4,5,6,3,7,6}; // 开数组存储0~9各个数字要用的火柴棍数
while (x / 10) // 当x/10不为0时,说明x不是一位数
{
num += f[x%10]; // 获取x的末尾数字并累加
x /= 10; // 去掉x的末尾数字
}
num += f[x]; // 循环结束后,不要忘记把x所需的火柴棍数也累加到num中
return num;
}
int main()
{
// 初始化&读入
int a, b, c, n, ans = 0;
cin >> n;
// 循环枚举两个加数a和b
for (a = 0; a <= 1111; a ++)
for (b = 0; b <= 1111; b ++)
{
c = a + b; // 计算出c的结果
if (fun(a)+fun(b)+fun(c) == n - 4) // 当fun(a)+fun(b)+fun(c)(a,b,c所需火柴棍数之和)等于n除去加号和等号所需的火柴棍(共4根),则找到了一组解
ans ++; // 累加结果
}
//输出
cout << ans;
}
```
by 攀岩高手 @ 2017-05-26 21:53:26
对不起我傻了,知道错哪了。错的很明显。。
by Usami_Hearn @ 2017-05-26 22:14:16
@[攀岩高手](/space/show?uid=43064) 谢谢
by Usami_Hearn @ 2017-05-26 22:24:55
@[攀岩高手](/space/show?uid=43064)
为何我的超时
```cpp
#include<iostream>
using namespace std;
int u[10]={6,2,5,5,4,5,6,3,7,6};
int use(int num)
{
int tot=0;
while(num/10)
{
tot+=u[num%10];
num/=10;
}
tot+=(u[num]);
return tot;
}
int main()
{
int ans=0,n;
cin>>n;
for(int i=0;i<=1000;i++)
for(int j=0;i<=1000;j++){
if(use(i)+use(j)+use(i+j)==n-4) ans++;
}
cout<<ans;
return 0;
}
```
by middle_set @ 2017-07-02 17:16:45