输入包括一行,一行中两个整数l和r(1 ≤ l, r ≤ 10^9, 0 ≤ r - l ≤ 10^6),以空格分割
输出一个整数,即区间内的神奇数个数
1 50
4
import java.util.*; public class Main { // 求从给定区间里找神奇数 public static void main(String[] args) { Scanner in = new Scanner(System.in); int cnt = 0; int l = in.nextInt(), r = in.nextInt(); for (int i = l; i <= r; i++) { if (fun(i)) { cnt++; } } System.out.println(cnt); } // 动态规划处理 public static boolean fun(int n) { int[] arr = new int[(n+"").length()]; int idx = 0; int sum = 0; while (n != 0) { arr[idx] = n % 10; // 数字按顺序放在数组里 sum += arr[idx]; idx++; n /= 10; } // 子集背包问题-转为0-1背包问题-> 224能不能凑出4问题 if (sum % 2 != 0) return false; int amount = sum / 2; boolean[] dp = new boolean[amount+1]; dp[0] = true; for (int num : arr) { for (int j = amount; j >= num; j--) { dp[j] = dp[j] || dp[j - num]; } } return dp[amount]; } }