SDNU 1270.超超的难题

Description

超超终于向他的女神小美表白了。可是小美只喜欢聪明的程序员，当场给他出了道难题，题目如下：给你n根火柴棍，你可以拼出多少个形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整数（若该数非零，则最高位不能是0）。用火柴棍拼数字0-9的拼法如图所示：

注意：
1. 加号与等号各自需要两根火柴棍
2. 如果A≠B，则A+B=C与B+A=C视为不同的等式（A、B、C>=0）
3. n根火柴棍必须全部用上
超超分分钟就解出来了。
亲爱的小伙伴们，你们是不是也可以分分钟搞定这道难题呢？

Input

一个整数N（ N <= 24），表示N根火柴棍

Output

可以拼出形如“A+B=C”的等式的个数。如果A≠B，则A+B=C与B+A=C视为不同的等式（A、B、C>=0）

Sample Input

Sample Output

Hint

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

Source

nanran

思路：这道及其神奇的题，要先打表，存下每个数对应的火柴数，然后再计算每个火柴数对应的等式数量。必须要计算火柴数1000的时候的量，不然这道题就wa

#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
using namespace std;
#define ll long long
const int maxn = 5100;

int n, a[10000], sum[10000];

void init()
{
    memset(a, 0, sizeof(a));
    a[0] = 6;
    a[1] = 2;
    a[2] = 5;
    a[3] = 5;
    a[4] = 4;
    a[5] = 5;
    a[6] = 6;
    a[7] = 3;
    a[8] = 7;
    a[9] = 6;
    for(int i = 10; i<1999; i++)
    {
        int miao = i;
        while(miao)
        {
            int buffer = miao%10;
            a[i] += a[buffer];
            miao /= 10;
        }
    }
    memset(sum, 0, sizeof(sum));
    for(int i = 0; i<1000; i++)
        for(int j = i; j<1000; j++)
            for(int k = 0; k<30; k++)
            {
                if(a[i]+a[j]>k-6)continue;
                if(a[i]+a[j]+a[i+j]+4 == k && i != j)
                    sum[a[i]+a[j]+a[i+j]+4] += 2;
                else if(a[i]+a[j]+a[i+j]+4 == k && i == j)
                    sum[a[i]+a[j]+a[i+j]+4] ++;
            }
}

int main()
{
    init();
    scanf("%d", &n);
    printf("%d
", sum[n]);
    return 0;
}