题目链接
题目概述
输入两个数 a、b，对于任意自然数 x、y，ax+by 所表示不出的最大整数是多少。
题目分析
看到大佬的文章，有如下结论：
a,b为质数，x,y为非负整数，则ax+by最大不能表示的数为ab-a-b。
但题目中似乎没说 a、b为质数，那就用动归吧。
完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include <bits/stdc++.h>
using namespace std;
const int MAXN=1e7+5;
bool dp[MAXN]={0};
int a,b,ans;
int main(){
cin>>a>>b;
dp[0]=dp[a]=dp[b]=true;
for(int i = 0; i < maxn - a - b; ++i) {
if(dp[i])
dp[i + a] = dp[i + b] = true;
else
ans = i;
}
cout<<ans<<endl;
return 0;
}
|
自我总结
一开始我是用这样的迭代来动归的：
1
2
3
4
5
6
| for(int i=max(a,b); i<MAXN-a-b; i++){
if(!dp[i])
dp[i]=(dp[i-a]||dp[i-b]);
if(!dp[i])
m=i;
}
|
这么写虽然能过，但是有问题的，如果 2a < b，那么会漏掉 [a, b] 之间能表示的数，所以还是应该像完整代码中那样顺推。