·【蓝桥】·买不到的数目

题目来源：买不到的数目
总结该题有三种解法：
[TOC]

问题描述
小明开了一家糖果店。他别出心裁：把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。
小朋友来买糖的时候，他就用这两种包装来组合。当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。
你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。大于17的任何数字都可以用4和7组合出来。
本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。
输入格式
两个正整数，表示每种包装中糖的颗数(都不多于1000)
输出格式
一个正整数，表示最大不能买到的糖数
样例输入1
4 7
样例输出1
17
样例输入2
3 5
样例输出2
7

数学知识

  • 典型的Ax+By=C问题（A、B及两个包装糖数量，C是总糖数），C未知情况下，讨论不定方程的解和C的取值的关系，我的另一篇博客上有详细总结：
    Ax+By=C的解的讨论(仅A,B为常数)

  • 该题求最大不能组合出的数字，也就是求导致Ax+By=C无解的C的最大值，于是可以得出一些隐含条件：
    ①方程存在无解，且无解的个数有限 ②考虑实际情况x、y均非负

  • 于是由数学知识得：
    所有输入样例均满足A、B互质，继而直接输出结果cout << A*B-(A+B)

枚举

如果不知道上面的数学知识，什么A、B互质的，本题可以通过枚举求解
算法思想

  • 既然导致不定方程无解的C有最大值max，那么可以确定一个C的上界MAX，然后枚举x和y，把小于这个上界MAX的可行解都枚举出来，最后从大往小的筛选即可。
  • 如何确定这个上界MAX? A和B既然都不大于1000，那就直接令MAX=A*B吧。
    ——————————————完整代码————————————————
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    #include <iostream>
    #include <set>

    using namespace std;

    int main(){
    	set<int> c;
    	int a, b;
    	cin >> a>> b;
    	for(int x = 0; a*x <= a*b; ++x){//上限a*b
    		for(int y = 0; a*x+b*y <= a*b; ++y){
    			c.insert(a*x+b*y);//用set将可行的c都枚举出来
    		}
    	}
    	for(int k = a*b; k >= 0; --k){//从大往小的筛选，找第一个不存在
    		if(c.find(k) == c.end()){
    			cout << k <<endl;
    			break;
    		}
    	}
    	return 0;
    }

动态规划

动态规划又是对上面枚举的高度总结：

  • 数组dp的长度沿用了上界MAX；
  • dp[i]为1，表示C取i是有解，反之为0，无解；
  • 直接上dp方程吧：dp[i] = (dp[i-a]||dp[i-b]) ? 1 : 0

——————————————完整代码————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <algorithm>

using namespace std;

int dp[1000005];
int main(){
	int a, b;
	cin >> a >> b;
	dp[a] = 1; dp[b] = 1;
	for(int i = max(a, b)+1; i < a*b; ++i){
		dp[i] = (dp[i-a] || dp[i-b]);
	}
	for(int i = a*b-1; i > 0; --i){//同样从大往小的筛选，找第一个为0的
		if(!dp[i]){
			cout << i << endl;
			break;
		}
	}
	return 0;
}