AcWing 1205. 买不到的数目
原题链接
简单
//ways 1 使用定理
// #include <iostream>
// using namespace std;
// int main() {
// int a,b;
// cin>>a>>b;
// cout <<(a-1)*(b-1)-1;
// }
// ways 2 使用dfs但是很可惜超时了
// //给定一个m,是否能用p和q凑出来 important
// bool dfs(int m,int p,int q)
// {
// if(m == 0) return true;
// if(m >= p && dfs(m - p,p,q)) return true;
// if(m >= q && dfs(m - q,p,q)) return true;
// return false;
// }
// int main()
// {
// int p,q;
// cin >> p >> q;
// int res = 0;
// for(int i = 1; i <= 1000;i ++)
// {
// if(!dfs(i,p,q)) res = i;
// }
// cout << res << endl;
// return 0;
// }
//ways 3 dp现在还没看懂
#include <iostream>
#include <algorithm>
using namespace std;
//两个数据分别是n,m,假定最小值是minn,最大值是maxx,那么就相当于从minn开始,不断往前走,
//每走到一个数,都要看看dp[i - n]或者dp[i - m]是否为true,如果是,则置true,
//反之我们需要更新ans,ans就是指最大不能买的数目,也就是我们最后的输出,循环结束,便可直接输出ans
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++) {//因为最大的数不会超过m*n
if (dp[i - minn]) {
dp[i] = true;
} else if (i >= maxx && dp[i - maxx]) {
dp[i] = true;
} else {
ans = i;
}
}
cout << ans;
return 0;
}