题目描述

小明开了一家糖果店。

他别出心裁：把水果糖包成4颗一包和7颗一包的两种。

糖果不能拆包卖。

小朋友来买糖的时候，他就用这两种包装来组合。

当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。

你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。

大于17的任何数字都可以用4和7组合出来。

本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。

输入格式
两个正整数 n,m，表示每种包装中糖的颗数。

输出格式
一个正整数，表示最大不能买到的糖数。

数据范围
2≤n,m≤1000，
保证数据一定有解。

输入样例：

4 7

输出样例：

17

我的思路: 猜测这个不能由n,m凑出来的数应该是不会超过n*m,至于证明，我是这样想的,反证法
假设不能被凑出的最大的数大于 n·m 即:x - n · m > 0
说明不存在任何一对a,b和d使得以下式子成立(由于x不能被凑出来所以加上一个d): x = a·n + b·m + d
代入上式计算得到：a·n + b·m + d - m·n > 0即此式不成立,我们可以取a = m,b = n上式变为 m·n + d > 0 可以发现这是必成立的(抛去0)与假设矛盾，所以x一定不大于n*m

dp思路：
由于不能确定a和b的值，我们就假设dp[i]为能否组成i 遍历一遍从min(n,m)到 n*m
时间复杂度$O(n)$

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1e7;

bool dp[N];
int n, m;

int main()
{
    cin >> n >> m;

    dp[0] = true;
    int a = min(n, m);
    int b = max(n, m);
    int res = 0;

    for(int i = a; i <= n * m; i ++ )
    {
        if(dp[i - a]) 
        {
            dp[i] = true;
        }else if(i >= b && dp[i - b])
        {
            dp[i] = true;    
        }else res = i;
    }
    cout << res << endl;
    return 0;
}

y总的nb思路:(a - 1)(b - 1) - 1
时间复杂度$O(1)$
考试时以我的智商，哼，那不存在的

#include <iostream>
#include <algorithm>

using namespace std;
int n, m;

int main()
{
    cin >> n >> m;
    cout << (n - 1)*(m - 1) - 1<< endl;
    return 0;
}