[NOIP2008 提高组] 火柴棒等式

[NOIP2008 提高组] 火柴棒等式

题目描述

给你 $n$ 根火柴棍，你可以拼出多少个形如 $A+B=C$ 的等式？等式中的 $A$、$B$、$C$ 是用火柴棍拼出的整数（若该数非零，则最高位不能是 $0$）。用火柴棍拼数字 $0～9$ 的拼法如图所示：

注意：

1. 加号与等号各自需要两根火柴棍；
2. 如果 $A\ne B$，则 $A+B=C$ 与 $B+A=C$ 视为不同的等式（$A,B,C\ge 0$）；
3. $n$ 根火柴棍必须全部用上。

输入格式

一个整数 $n(1\le n\le 24)$。

输出格式

一个整数，能拼成的不同等式的数目。

样例 #1

样例输入 #1

14

样例输出 #1

2

样例 #2

样例输入 #2

18

样例输出 #2

9

提示

【输入输出样例 1 解释】

$2$ 个等式为 $0+1=1$ 和 $1+0=1$。

【输入输出样例 2 解释】

$9$ 个等式为

$0+4=4$、$0+11=11$、$1+10=11$、$2+2=4$、$2+7=9$、$4+0=4$、$7+2=9$、$10+1=11$、$11+0=11$。

noip2008 提高第二题

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1010;
int path[N]; // 存储路径
int n;
int sums[N] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; // 存储火柴数

int res; // 方案数

void dfs(int x, int sum){
    if(sum > n) return ; // 剪枝
    
    
    if (x > 3){
        if ((path[1] + path[2] == path[3]) && sum == n){
            // for (int i = 1; i <= 3; i ++)
            //     printf("%d ", path[i]);
            // puts("");
            res ++;
        }
        
        return ;
    }
    
    for (int i = 0; i <= N; i ++){
        path[x] = i;
        dfs(x + 1, sum + sums[i]);
        
        // 回溯
        path[x] = 0;
    }
}

int main(){
    scanf("%d", &n);
    n -= 4; // 去掉=号和+号所用的四根火柴
    
    // 预处理每个数所需要的火柴数
    for (int i = 10; i <= N; i ++){
        sums[i] = sums[i % 10] + sums[i / 10];
    }
    
    dfs(1, 0);
    
    printf("%d\n", res);
    
    return 0;
}