【递推】C000_openj_火柴棒等式（暴力）

一、Problem

Input

输入一个整数n（n≤24）。

Output

输出能拼成的不同等式的数目。

二、Solution

方法一：暴力枚举

• 最多 24 根火柴棒，加号 + 与等号 = 各占 2 根火柴棒，推出 A B C 一共最多占 20 根。
• 确定上界：如果要分析两个数的界限，一般的做法就是先让其中一个数取最小，然后，分析另一个数的上界。
  • 数字 1 是最少花费的，只需要 2 根火柴棒表示，又 A <= C，而 20 根全要用上可以表示的总和最小组合数为：A(1111) + B(1) = C(1112)。所以 A / B 数值的下界是 0，火柴棒的使用数量的上界是 1111，但因为 A 与 B 不同时，算两种答案，所以两个数都要枚举到 1111

import java.util.*;
import java.math.*;
import java.io.*;
public class Main {
	static int[] A = {6,2,5,5,4,5,6,3,7,6};
	static int N;
	
	static int need(int n) {
		if (n == 0)
			return A[0];
		int s = 0;
		while (n >= 1) {
			s += A[n%10];
			n /= 10;
		}
		return s;
	}
    public static void main(String[] args) throws IOException {  
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
		N = sc.nextInt() - 4;
		int cnt = 0;
		for (int a = 0; a <= 1111; a++)
		for (int b = 0; b <= 1111; b++) {
			if (need(a) + need(b) + need(a+b) == N)
				cnt++;
		}
		System.out.println(cnt);
    }
}

预处理1：没看懂

for(i=10;i<1000;i++)a[i]=a[i/10]+f[i];

预处理2：先求出 0-2223 的所需棒数。

...

复杂度分析

• 时间复杂度：$O(...)$O(...)，
• 空间复杂度：$O(...)$O(...)，