买不到的数目

买不到的数目

小明开了一家糖果店。

他别出心裁：把水果糖包成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  = 1000010;
	static boolean [] f = new boolean [];
	public static void main(String[] args) {
		Scanner in = new Scanner (System.in);
		int n = ();
		int m = ();
		int mi = (n, m);
		int ma = (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;
		}
		println(res);
	}
}