蓝桥杯 prev8 买不到的数目

蓝桥杯 prev8 买不到的数目

问题描述

小明开了一家糖果店。他别出心裁:把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。 小朋友来买糖的时候,他就用这两种包装来组合。当然有些糖果数目是无法组合出来的,比如要买 10 颗糖。 你可以用计算机测试一下,在这种包装情况下,最大不能买到的数量是17。大于17的任何数字都可以用4和7组合出来。 本题的要求就是在已知两个包装的数量时,求最大不能组合出的数字。

输入格式

两个正整数,表示每种包装中糖的颗数(都不多于1000)

输出格式

一个正整数,表示最大不能买到的糖数

样例输入

4 7

样例输出

17

样例输入

3 5

样例输出

7

参考解答

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

using namespace std;

int main() { // 01背包,DP,自底向上
int t1, t2, dp[100001] = { 0 }, maxn = 100000;
cin >> t1 >> t2;
int t[2] = { t1,t2 };
for (int i = 0; i < 2; i++)
for (int j = t[i]; j <= maxn; j++)
dp[j] = max(dp[j], dp[j - t[i]] + t[i]);
for (int i = maxn; i >= 0; i--)
if (dp[i] < i) {
cout << i; // t1 * t2 - t1 - t2 貌似是整数互质的性质
break;
}
return 0;
}

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×