[蓝桥杯][2013年第四届真题]买不到的数目

题目

题目链接

题解

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

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

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

代码

#include
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