A12 正经题解

题意分析
用 $n$ 根火柴棒拼等式 $A+B=C$，求有多少种拼法。
解题思路
首先看到数据范围，第一个想到的就是打表枚举，那枚举什么呢？肯定是 $ABC$ 了。能确定的是需要 $4$ 根火柴棒拼符号，因此我们有至多 $20$ 根火柴棒来拼 $ABC$。一看好像很多，最少花费的数字是1，最高能到 $10$ 位数！事实并非如此，以下是上界推导，也是本题难点：

设 $A=1$（最小火柴 $2$ 根），$s(N)$ 为拼 $N$ 所需要的火柴数
推出 $a+b+c ≤ 20$，$B=C-1$，所以 $s(C)+s(C-1) ≤ 18$
假设一个枚举上界 $C≤2000$，对 $C≥2000$ 上述等式不成立，所以可以证明上界 $C≤2000$ 可用
当 $A$ 不是 $1$ 时，所需火柴更多，不等式更严
所以在 $n≤24$ 时，$C$ 最大不超过 $2000$

当然，也可以根据数据范围猜测数较小
接下来是就是实现，既然已经知道了数据范围，就可以根据范围来枚举。若枚举 $ABC$ 并在枚举时计算火柴棒花费则可能会超时，可以先把所有 $ABC$ 的可能值，也就是 $2000$ 以下的所有数字需要的火柴棒数量计算出来，可以节省大量时间。枚举 $a$ 和 $b$ 各自最多约 $1500$ 种可能，大概 $2e6$ 的计算量，不会超时
AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 3000; 
//保守的上界，实际我看其他题解2000也可以，上面思路部分也写了证明
int n, cnt=0;
int cost[N] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; 
//每个数字的花费

int main(){
    cin >> n;
    for(int i=10;i<N;++i){
        int t = i;
        while(t>=1){
            cost[i] += cost[t%10];
            t /= 10;
        }
    }
    for(int a=0;a<=N/2;++a){
        for(int b=0;b<=N/2;++b){
            if(cost[a]+cost[b]+cost[a+b]+4==n)
                cnt++;
        }
    }
    cout << cnt;

    return 0;
}