题目

题目链接

题解

暴力 or 动态规划？
想不出什么技巧，所以直接暴力（动态规划）的。

---

有点类似于动态规划的思想，本质还是暴力。

dp[i]表示i这个数能不能由输入的a和b构成，0表示不能，1表示可以。
转移方程：dp[i] = (dp[i-a] || dp[i-b])，当前这个数要么是前面某个数加a构成要么是加b构成。
初始化：比a和b中最小的还小的数没法被构成，比小者大且比大着小的，即位于俩数之间的数也没法被构成，a和b可以被构成。对于剩下的数遍历递推就行了。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;

int dp[N], ans, a, b;

int main()
{
	cin>>a>>b;
	int mn = min(a, b), mx = max(a, b);
	dp[mn] = dp[mx] = 1;
	for(int i = 0;i < mn;i ++) dp[i] = 0;
	for(int i = mn+1;i < mx;i ++) dp[i] = 0;	
	for(int i = mx+1;i < N-10;i ++) dp[i] = (dp[i-a] || dp[i-b]), ans = (dp[i]==0?i:ans);
	cout << ans << endl;
	return 0;
}