前言
这道题用那个(a - 1)(b - 1) - 1是快，但比赛时未必知道这个结论，那个时候现推出这个结论感觉也有点难，数学大神绕过。然后暴力dfs感觉有点太暴力，也会有超时风险，因此考虑dp方法
算法分析
先开一个bool类型dp数组，dp[i]表示能否组成i。
两个数据分别是n,m，假定最小值是minn，最大值是maxx，那么就相当于从minn开始，不断往前走，每走到一个数，都要看看dp[i - n]或者dp[i - m]是否为true，如果是，则置true，反之我们需要更新ans，ans就是指最大不能买的数目，也就是我们最后的输出，循环结束，便可直接输出ans
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;
}
ans初始化为1就好了
数据保证了有解，ans=1直接过了2 3问题，赞
可以把ans初始化为ans=min-1;
应该是有bug的吧，2 3没检测到这个数据
数据保证有解....2 3好像是无解
2 ,3是有解的吧，2和3不能拼出来的最大的数为1，而如果你用dp这个方法写，输出答案为0
结合题目的实际意思来讲，若为2,3就不可能有1这个情况，能包出的糖果数至少也是2，理解不同罢了
属实妙，佩服
希望能看到不大于n*m的证明害
猜测这个不能由n,m凑出来的数应该是不会超过nm,至于证明，我是这样想的,反证法
假设不能被凑出的最大的数大于 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一定不大于nm
tql！！！
x不能被凑出来不应该是存在a,b,d使式子成立吗
灯子，我的灯子o(￣︶￣)o
贴贴！
兄弟，你的反证法不太对，反证法应该是假设结论正确，根据假设的结论再往前推，然后推出条件错误
你这里假设存在，那就应该顺着这个结论去找，而不是否定这个结论再去找条件
假设错了，应该是存在一对使结果成立
2≤n,m≤1000，可以把ans初始为1
不初始是过不了的
n*m是上限 看评论有点解释不清的样子
吊啊，直接swap又少一行
其实直接暴力就行hh
上限为什么是n*m?
我是这样想的，可能是因为他在不停地减，就是本身的bool值由它本身减去一个maxx或minn来决定，这样的话由他本身减去一个maxx或minn的bool值又可以由它再减去一个minn或maxx来决定，这样循环往复总能循环到nm以下的区域（nm有点类似与上界）
好像不能这样理解，我错了抱歉
好像也可以这样理解了。。。这样的话也可以认为凡是大于nm的都可以由一个小于nm的数加上一个nm的倍数来表示，由于是加上了一个nm的倍数，假设大于nm的数符合条件的话，那么2nm,3n*m.....不就都无解了吗，这样的话没法算出来最大值
证明确实不严谨
如m，n为4.5
不能凑出最大的是11
但是对于4×5×2+11＝51＝4×9+5×3就凑出来了。也就是说这个反证法不对
请问一下为什么dp的大小要设置成1000000呢？我用了INT32_MAX过不了
好像是数据范围吧，按他的意思n*m最大1000的两次方
各位大佬请问为什么这段代码在测试14 41这个数据的时候不会SF(保证m>n)？
如果i<m,会发生数组越界
基于卖糖果这件事，2 3肯定凑不出1来啊，如果是 -12+13，又怎么会有-1袋糖果···
zan
nb
高手高手
感觉有一个BUG，比如n=2,m=3，凑不到的最大的数是1,但是题解里的ans是从2开始判断的。。我感觉 ans应该从1开始判断，1到n，n到m，m到n*m这样，不知道说的对不对，，，
没有影响的，除非n或m里有一个1，不然无论如何1都取不到，如果有一个1的话第一次循环就把dp【1】置为true了
if(dp[i-n] || dp[i-m] ){
dp[i]=true;
}else{
res=i;
}
这样写的代码是错误的，为什么一定要中间在做一个判断才可以ac呢？求解答
i-m可能会越界
秒啊
为什么ans <= a*b呀 ？？
说实话想法不够严谨，你可以理解为1~nm为一个循环周期，也就是从nm+1 ~ 2nm这个周期开始，其中任何一个数都可以由第一个周期对应的数加上nm得到。那么如果最大不可凑成的数超过nm，比如nm+k，那么2nm+k，3n*m+k也必然凑不出来，不就无解了吗，这只是个人不太严谨的推理哈~~~
举个例子1~60为第一个周期，假如67凑不出来，那么7肯定是凑不出来的，但同时127，187也必然凑不出来啦
你可以尝试证明一下最大不可凑成的数不会超过mn😄
nb
 回复
证明确实不严谨
如m，n为4.5
不能凑出最大的是11
但是对于4×5×2+11＝51＝4×9+5×3就凑出来了。也就是说这个反证法不对
2 3过不了，得从1开始