daily

用户名：weightless

访问量：1296

签　名：

Hello world！

等　　级
排　　名	11700
经　　验	1013
参赛次数	5
文章发表	2
年　　龄	15
在职情况	学生
学　　校	绍兴鲁迅中学
专　　业

　　自我简介：

热爱计算机，目前正处于入门阶段（QQ号 3205177338）

TA的其他文章

最大体积（动态规划补空隙C++）
浏览：426

你可能喜欢

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

C语言程序设计教程（第三版）课后习题8.9 （C++代码）（其实不需要开数组，一个一个字符读入并判断就好了）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）如果a<0，那就不是这个代码了，哈哈哈哈

优质题解

最大体积（动态规划补空隙C++）

　　作者: daily　　　　发表时间：2022-02-09 09:56:32 浏览：426　|　评论：4　

原题链接：蓝桥杯算法训练VIP-最大体积

1. - 分析问题
首先，由扩展欧几里得算法，可以得出若x,y为正整数a,b为整数，**则ax+by=1有解是x与y互质的充要条件。**
所以当给出的体积互质时（所有体积的最大公约数为1），一定有解；反之无解。
由此，可以先计算所有给出体积的最大公约数，判断是否有解，确定有解后进行下一步计算。于是定义了函数gcd和haveanswer两个函数，在haveanswer中调用gcd，来计算所有给出体积的最大公约数。返回最大公约数x==1的布尔值，有解情况下即返回true。
如果有解，下一步，分析如何进行动态规划。以样例为例，3,6,10三个体积，用可能组成的体积作为i，取的物体的数量作为j，dp[i][j]表示取j个物体时是否能组成体积i（布尔值）。得到：
>j=1时，dp[3,6,10][1] = 1;
j=2时，dp[3,6,9,12,13,16,20][2] = 1;
j=3时，dp[3,6,9,12,13,15,16,18,19,20,22,23,26,30][3] = 1;

没必要再往下了。由18,19,20，三个连续的数字，我们发现18+3=21,19+3=22,20+3=23,21+3=24,22+3=25...如此像履带一样像前碾压，后面的所有体积将会被组成，由此得到不能组成的最大体积为17，于是得到：
>当该问题有解时，视给出的最小体积为最小空隙，由动态规划得到的第一次能组成的连续体积个数等于给出的最小体积时，最小空隙被填补，于是后面所有体积都可以组成，这组连续体积中最大的体积减去给出的最小体积即为不能组成的最大体积。

- 参考代码

```cpp
#include<iostream>
#define MAX 200000001
using namespace std;
bool dp[MAX];

int min(int n, int a[]) { //找出最小空隙
	int m = a[0];
	for(int i = 1; i < n; i++)
		if(a[i] < m)
			m = a[i];
	return m;
}

int gcd(int a, int b) {  //最大公约数
	return b == 0 ? a : gcd(b, a % b);
}

bool haveanswer(int n, int a[]) {  //计算是否有解
	int x = gcd(a[0], a[0]);  //这样是为了防止数组越界
	for(int i = 1; i < n; i++) {
		x = gcd(a[i], x);
	}
	return x == 1;
}

int main() {
	int n, *a, maxv = 0;  //记录下给出的最大的体积 
	scanf("%d", &n);
	a = new int[n];
	for(int i = 0; i < n; i++) {
		scanf("%d", a + i);
		dp[a[i]] = 1;  //标记下原有体积 
		maxv = a[i] > maxv ? a[i] : maxv;
	}
	if(!haveanswer(n, a)) {
		printf("%d", 0);
		return 0;
	}
	int ans = 0, minsep = min(n, a), answer = 0, i = minsep - 1;  //ans:连续体积的个数;minsep:最小空隙;answer:答案;i:递增体积 
	while(++i) {
		if(dp[i]) {
			ans++;
			if(ans == minsep) {  //找到啦！！！ 
				answer = i - minsep;
				break;
			}
			for(int j = 0; j < n; j++) {
				dp[i + a[j]] = 1;
			}
		} else
			ans = 0;
	}
	if(answer >= MAX)  //超出范围视作无解 
		answer = 0;
	printf("%d", answer);
	return 0;
}
```
PS：请多指教，感谢阅读！！！

0.0分

43 人评分

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

　　评论区

BITxiaohao

开个两亿的空间？

2022-11-22 18:21:28

violinwang

不超时的前提 是不是 这个不能表示的最大的数字 不能太大，而且是肯定不能达到题目中的有限解上限？
那这个 解  的范围是不是在本题中是一定的？

2022-02-19 19:58:18

violinwang

这是人能想出来的吗？！tql

2022-02-19 19:50:02

流氓抠脚

真TM的好

2022-02-09 23:09:18

daily

TA的其他文章

你可能喜欢

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

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

C语言程序设计教程（第三版）课后习题8.9 （C++代码）（其实不需要开数组，一个一个字符读入并判断就好了）

C二级辅导-分段函数（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）如果a<0，那就不是这个代码了，哈哈哈哈

最大体积（动态规划补空隙C++）

评论区

精彩推荐

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

大神老白（C语言代码）

母牛的故事（C语言代码）

【魔板】（C++代码）(时间超限，希望会的帮我改正一下)

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

字符逆序（C语言代码）

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

The 3n + 1 problem （C语言代码）

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

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

daily

TA的其他文章

你可能喜欢

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

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

C语言程序设计教程（第三版）课后习题8.9 （C++代码）（其实不需要开数组，一个一个字符读入并判断就好了）

C二级辅导-分段函数 （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码） 如果a<0，那就不是这个代码了，哈哈哈哈

最大体积（动态规划补空隙C++）

评论区

精彩推荐

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

大神老白 （C语言代码）

母牛的故事 （C语言代码）

【魔板】 （C++代码）(时间超限，希望会的帮我改正一下)

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

字符逆序 （C语言代码）

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

The 3n + 1 problem （C语言代码）

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

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

C二级辅导-分段函数（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）如果a<0，那就不是这个代码了，哈哈哈哈

　　评论区

大神老白（C语言代码）

母牛的故事（C语言代码）

【魔板】（C++代码）(时间超限，希望会的帮我改正一下)

字符逆序（C语言代码）