小行星

用户名：theasteroid

访问量：1297

签　名：

等　　级
排　　名	13261
经　　验	932
参赛次数	0
文章发表	5
年　　龄	0
在职情况	学生
学　　校	芜湖大学
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2019年第十届省赛真题-人物相关性分析（滑动窗口）
浏览：294

蓝桥杯2019年第十届省赛真题-扫地机器人(二分)
浏览：397

你可能喜欢

带限制条件的分组背包

　　作者: 小行星　　　　发表时间：2022-04-06 08:56:24 浏览：261　|　评论：0　

原题链接：蓝桥杯2020年第十一届省赛真题-装饰珠

```C++
#include <iostream>
#include <algorithm>

/*
	思路：首先尝试将问题简化，如果去掉等级这一限制，那么所有的装饰孔可以合并成一个体积为V的背包，对于下面m组t个物品，我们只选择每组中的一个，求最大价值。很明显，一旦去掉等级的制约后，这是一个经典的分组背包问题，所以我们的思路就是背包的同时，巧妙规避掉等级的限制————使用贪心策略。
	
	这题主要有两点贪心：
	1. 题意中一组物品可以无限选，但是找过t后不会提供额外价值，显然我们没必要枚举t+1...t+n以后的物品，总价值不会增加，不如把宝贵的空间留下来，并且背包容积足够，这组物品也顶多贡献w[t]资源
	2. 我们需要把所有的装饰孔放入一个数组，另一个结构体数组存放每组物品，全按照等级升序排列。那么我们按照老套路进行分组背包dp，使用滚动数组，倒序枚举装饰孔得到f[j]=max(f[j], f[p] + w[k]), j表示第几个装饰孔，p和j构成[p,j]区间满足区间等级>=该组物品，并且区间长度>=k，k表示每组第k个物品。因为装饰孔是有序的，所以p可以O(1)算出, 并且基于贪心思想，p减少f[p]也会减少，w[k]不变，因此我们只要第一个p就足够了，不需要继续枚举；每组物品等级是升序的，大等级f[j]可能会用到小等级更新的f[j]，如果无序,观察状态转移方程可知，如果不多加一个循环，那么小等级无法利用到大等级更新的f[j],所以每组物品也需要排序。
	
	以上分析结束，代码如下：
*/
const int MAXN = 1000;
int n, m, a[MAXN];
int f[MAXN];
struct Nd{
	int s, t, w[10];
	bool operator<(const Nd& n) const{
		return s < n.s;
	}
} b[10001];

int main(){
	for(int i = 1; i <= 6; i++) {
		int t; std::cin >> t;
		while(t--){
			++n;
			std::cin >> a[n];
		}
	}
	
	std::cin >> m;
	for(int i = 1; i <= m; i++){
		std::cin >> b[i].s >> b[i].t;
		for(int k = 1; k <= b[i].t; k++) std::cin >> b[i].w[k];
	}
	
	std::sort(a+1, a+n+1);
	std::sort(b+1, b+m+1);
	
	for(int i = 1; i <= m; i++){
		for(int j = n; j > 0; j--){
			for(int k = 1; k <= b[i].t; k++){
				int p = j - k + 1;
				if(a[j] >= b[i].s && p >= 1 && a[p] >= b[i].s){
					f[j] = std::max(f[j], f[p-1] + b[i].w[k]);
				}
			}
			
		}
	}
	std::cout << f[n] << std::endl;
	return 0;
}
```

0.0分

13 人评分

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

小行星

TA的其他文章

你可能喜欢

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

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

明明的随机数（C++代码）

蛇行矩阵（C语言代码）

数列（C++代码）

带限制条件的分组背包

评论区

精彩推荐

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

C语言训练-素数问题（C语言代码）

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

WU-字符串比较（C++代码）

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

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

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

Tom数（C语言代码）

蚂蚁感冒（C语言代码）

1050题解（结构体数组与结构体指针的使用）

小行星

TA的其他文章

你可能喜欢

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

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

明明的随机数 （C++代码）

蛇行矩阵 （C语言代码）

数列 （C++代码）

带限制条件的分组背包

评论区

精彩推荐

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

C语言训练-素数问题 （C语言代码）

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

WU-字符串比较 （C++代码）

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

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

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

Tom数 （C语言代码）

蚂蚁感冒 （C语言代码）

1050题解（结构体数组与结构体指针的使用）

明明的随机数（C++代码）

蛇行矩阵（C语言代码）

数列（C++代码）

　　评论区

C语言训练-素数问题（C语言代码）

WU-字符串比较（C++代码）

Tom数（C语言代码）

蚂蚁感冒（C语言代码）