P1149 [NOIP2008 提高组] 火柴棒等式

#include <bits/stdc++.h>
using namespace std;
const int maxn = 10005;
int n, m;
int ans = 0; // 记录方案数
int t[4];
int a[10010] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6, 8};
int math1(int r)
{ // 计算火柴棒个数
   if (a[r] > 0)
   {
      return a[r];
   }
   else
   {
      int an = 0;
      while (r != 0)
      {
         an += a[(r % 10)];
         r = r / 10;
      }
      return an;
   }
}
void dfs(int x, int sum) // 三个位置的第几个位置
{
   if (sum > n) // 剪枝！！！
      return;
   if (x > 3)
   {
      if (t[1] + t[2] == t[3] && sum == n)
      {
         ans++;
      }
      return;
   }
   for (int i = 0; i <= 1000; i++)
   {
      t[x] = i;
      dfs(x + 1, sum + math1(i));
      t[x] = 0;
   }
}
int main()
{
 
   scanf("%d", &n);
   n = n - 4; // 先把n处理了，不然最后一个点会超时
   dfs(1, 0);
   printf("%d", ans);
}

#include <bits/stdc++.h>
using namespace std;
const int maxn = 10005;
int n, m;
int ans = 0; // 记录方案数
int t[4];
int a[10010] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6, 8};
void dfs(int x, int sum) // 三个位置的第几个位置
{
   if (sum > n) // 剪枝！！！
      return;
   if (x > 3)
   {
      if (t[1] + t[2] == t[3] && sum == n - 4)
      {
         ans++;
      }
      return;
   }
   for (int i = 0; i <= 1000; i++)
   {
      t[x] = i;
      dfs(x + 1, sum + a[i]);
      t[x] = 0;
   }
}
int main()
{
   scanf("%d", &n);
   n = n;
   for (int i = 10; i <= 10000; i++)
   {                                // 递推出10~1000所需的火柴棒个数
      a[i] = a[i % 10] + a[i / 10]; // 优化！
   }
   dfs(1, 0);
   printf("%d", ans);
}