P1149_火柴棒等式（JAVA语言）

题目描述

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

注意：

1. 加号与等号各自需要两根火柴棍

2. 如果A≠B，则A+B=C与B+A=C视为不同的等式(A,B,C>=0)

3. n根火柴棍必须全部用上

输入输出格式

输入格式：

一个整数n(n<=24)。

输出格式：

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

输入输出样例

输入样例#1： 复制

14

输出样例#1： 复制

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

方法一：将1-1000的所需火柴数目表示出即可（时间复杂度高）

import java.util.*;
public class Main {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int a[]={6,2,5,5,4,5,6,3,7,6};
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        n-=4;
        int b[]=new int[1005];
        for(int i=0;i<1001;i++)
        {
            int j=i;
            do{
                b[i]+=a[j%10];
                j/=10;
                
            }while(j!=0);
        }
        int sum=0;
        for(int i=0;i<1001;i++)
        {
            for(int j=0;j<1001;j++)
            {
                for(int k=0;k<=1001;k++)
                {
                    if(i+j==k&&b[i]+b[j]+b[k]==n)
                    {
                        sum++;
                    }
                }
            }
        }
        System.out.println(sum);
    }

}

方法二：为了降低时间复杂度，可直接打表

import java.util.*;
public class Main {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int a[]={0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,8,9,6,9,29,39,38,65,92,128};
        
        System.out.println(a[n]);
    }

}