买不到的数目
小明开了一家糖果店。
他别出心裁：把水果糖包成4颗一包和7颗一包的两种。
糖果不能拆包卖。
小朋友来买糖的时候，他就用这两种包装来组合。
当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。
你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。
大于17的任何数字都可以用4和7组合出来。
本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。
输入格式
两个正整数 n,m，表示每种包装中糖的颗数。
输出格式
一个正整数，表示最大不能买到的糖数。
数据范围
2≤n,m≤1000，
保证数据一定有解。
输入样例：
4 7
输出样例：
17
算法思路：
先开一个bool类型dp数组，dp[i]表示能否组成i。
两个数据分别是n,m，假定最小值是minn，最大值是maxx，那么就相当于从minn开始，不断往前走，每走到一个数，都要看看dp[i - n]或者dp[i - m]是否为true，如果是，则置true，反之我们需要更新ans，ans就是指最大不能买的数目，也就是我们最后的输出，循环结束，便可直接输出ans.
特解答案：
#include<iostream> using namespace std; int main() { int a, b; cin >> a >> b; cout << a * b - a - b; return 0; }
正常解C++
#include <iostream> #include <algorithm> using namespace std; int n, m, minn, maxx, ans; bool dp[1000000]; int main() { cin >> n >> m; dp[0] = true; minn = min(n, m); maxx = max(n, m); for (int i = minn; i < n * m; i++) { if (dp[i - minn]) { dp[i] = true; } else if (i >= maxx && dp[i - maxx]) { dp[i] = true; } else { ans = i; } } cout << ans; return 0; }
正常解Java
import java.util.*; public class Main { static int N = 1000010; static boolean [] f = new boolean [N]; public static void main(String[] args) { Scanner in = new Scanner (System.in); int n = in.nextInt(); int m = in.nextInt(); int mi = Math.min(n, m); int ma = Math.max(n, m); int res = 0; f[0] = true; for (int i = mi; i <= n * m; ++ i) { if (f[i - mi]) f[i] = true; else if (i >= ma && f[i - ma]) f[i] = true; else res = i; } System.out.println(res); } }
