zjh

用户名：speaksoftly

访问量：24718

签　名：

搞spring去了...不能愉快的刷题了...

等　　级
排　　名	172
经　　验	6955
参赛次数	10
文章发表	37
年　　龄	0
在职情况	学生
学　　校	海南
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2017年第八届真题-合根植物（C++代码）并查集
浏览：805

蓝桥杯2017年第八届真题-分考场（C++代码）图的染色
浏览：995

蓝桥杯2017年第八届真题-发现环（C++代码）并查集
浏览：1057

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

蓝桥杯2017年第八届真题-包子凑数 -题解(C++代码) 完全背包 + 暴力 + 空间优化

　　作者: zjh　　　　发表时间：2019-08-07 00:08:33 浏览：1274　|　评论：0　

原题链接：蓝桥杯2017年第八届真题-包子凑数

```cpp
思路：所有背包类问题，一定要知道一点，当前第i个物品进不进背包，进背包后的结果是不是最优的，背包ok之后再来一波暴力，直接甩个背包容量100W，如果超过10w个数拼不出来，就认为有无限个数拼不出来
空间优化：滚动数组

ps:实际上这道题是欧几里得 + 背包的题
首先如果N种蒸笼的包子数是互质的，那么是有限的。如果不是互质的，那么直接输出INF即可。
如果是互质的，我们dp[0] = true;
之后用n个包子暴力遍历1~100W，看看哪些数能能凑出来即可

#include "iostream"
#include "cstdio"
#include "cstdlib"
#include "cstring"
#include "cmath"
#include "algorithm"
#include "queue"
#include "vector"
#include "stack"
#include "map"
#include "set"
using namespace std;
typedef long long ll;
const int maxn = 1000010;
const int INF = 1e9;

int n;
bool dp[maxn + 1];

int main() {
	cin >> n;
	bool flag = false;
	dp[0] = true;
	for(int i = 0; i < n; ++i) {
		int x;
		cin >> x;
		//如果有1，那么所有数都可以拼出来，就坐等输入完直接输出INF了
		if(x == 1) flag = true;
		if(!flag)	//如果目前还没有1，那就完全背包
		//完全背包从x....maxn滚动
			for(int j = x; j <= maxn; ++j) dp[j] |= dp[j - x];
	}
	if(flag) {
		cout << 0 << endl;
		return 0;
	}
	int res = 0;
	for(int i = 1; i <= maxn; ++i) if(!dp[i]) res++;	//统计拼不出来的个数
	if(res >= 100000) cout << "INF" << endl;
	else cout << res << endl;
	return 0;
}
```

0.0分

8 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

zjh

TA的其他文章

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C++代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

字符串的输入输出处理（C语言代码）

点我有惊喜！你懂得！

蓝桥杯2017年第八届真题-包子凑数 -题解(C++代码) 完全背包 + 暴力 + 空间优化

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

矩阵乘法（C++代码）

简单的a+b （C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

WU-整除问题（C++代码）

简单的a+b （C语言代码）

1124题解

字符串比较（C语言代码）

C语言程序设计教程（第三版）课后习题12.3 （C语言代码）

zjh

TA的其他文章

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C++代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

字符串的输入输出处理 （C语言代码）

点我有惊喜！你懂得！

蓝桥杯2017年第八届真题-包子凑数 -题解(C++代码) 完全背包 + 暴力 + 空间优化

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

矩阵乘法 （C++代码）

简单的a+b （C语言代码）

C语言训练-求1+2!+3!+...+N!的和 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

WU-整除问题 （C++代码）

简单的a+b （C语言代码）

1124题解

字符串比较 （C语言代码）

C语言程序设计教程（第三版）课后习题12.3 （C语言代码）

字符串的输入输出处理（C语言代码）

　　评论区

矩阵乘法（C++代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

WU-整除问题（C++代码）

字符串比较（C语言代码）