首页 > 其他分享 >252 摸鱼 压缩dp

252 摸鱼 压缩dp

时间:2024-11-06 14:42:42浏览次数:1  
标签:11 20 int li 蜗蜗 摸鱼 252 dp

/*
http://oj.daimayuan.top/course/5/problem/252
蜗蜗一共有 n天假期,在假期的第 i天摸鱼他会得到 ai的快乐值。
如果蜗蜗每天都摸鱼的话,他会有愧疚感,所以蜗蜗制定了这么个计划:
对于每一天,蜗蜗都有一个列表,如果蜗蜗在列表中的每一天都在摸鱼的话,这一天蜗蜗就不能摸鱼。
现在请问蜗蜗如何摸鱼,使得他能获得的快乐值总和最大?请求出快乐值总和最大是多少。

输入格式
第一行一个整数 n表示天数。

第二行 n个整数 a1,a2,...,an。

接下来 n行,对于第 i行,先读入一个整数 li表示第 i天的列表上有几天。
如果 li=0,也就是列表是空的话,表示第 i天没有限制;
否则,再读入 li个数表示列表上列的分别是第几天,数据保证这 li个数两两不同并且都不等于 i。

输出格式
一行一个整数表示答案。

样例输入
4
1 2 3 4
0
1 1
1 2
2 2 3
样例输出
8


20
2 2 9 5 9 3 1 5 8 2 1 6 7 9 3 2 3 2 4 3
5 2 4 5 11 17
5 1 5 7 9 3
1 2
2 2 13
1 20
6 1 2 3  8 15 20
4 11 12 13 14
4 20 19 18 17
6 1 20 5 15 13 12
1 2
1 3
3 4 7 9 
1 5
1 6
2 9 11 
2 9 12
2 8 14
2 5 16
1 3
11 1 3 5 7 9 8 11 15 16 17 18


数据范围
对于 100%的数据,保证 2≤n≤20,1≤ai≤100000,0≤li<n。
*/

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>


using namespace std;

const int N = 21;
int a[N];
int n; int ans = 0;
int limit[N];


void dfs(int idx, int status) {
	if (idx == n) {
		for (int i = 0; i < n; i++) {
			if (status & (1 << i)) {
				//检查
				if (limit[i] == 0) continue;
				if ( (status & limit[i]) == limit[i]) {
					return;
				}
			}
		}
		int sum = 0;
		for (int i = 0; i < n; i++) {
			if (status & (1 << i)) {
				sum += a[i];
			}
		}

		ans = max(ans, sum);
		return;
	}


	//当前天数选择 
	dfs(idx + 1, status | (1 << idx));

	//当前天数不选择
	dfs(idx + 1, status);
}



int main()
{
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < n; i++) {
		int t;
		cin >> t;
		for (int j = 0; j < t; j++) {
			int b; cin >> b;
			limit[i] |= 1 << (b - 1);
		}
	}

	dfs(0, 0);

	cout << ans << endl;

	return 0;
}

标签:11,20,int,li,蜗蜗,摸鱼,252,dp
From: https://www.cnblogs.com/itdef/p/18530181

相关文章

  • IT人#摸鱼计划#,11月更文好礼来啦
     11月摸鱼计划如期而至,全新上线3款活动任务,还有多重奖励等你来拿!【活动时间】发文时间:2024年11月6日—2024年11月30日【活动任务】以下任务福利可同享!!同时,我们为大家整理了容易被百度收录的关键词,当你写作的时候,可以直接选择热点且擅长的关键词进行博文创作。 直达热点关键词库>......
  • 详解UDP协议
    UDP是一种无连接的、简单的传输层协议,UDP协议的设计目的是提供一种简单、轻量级的通信机制,适用于那些对实时性和传输效率有较高要求,但对数据完整性和可靠性要求相对较低的应用。UDP协议报头UDP协议的报头部分由四部分组成:源端口号,目的端口号,UDP长度,校验和。源端口号:识别发......
  • WordPress修改网站地址,WordPress网站地址更改步骤
    修改WordPress网站的地址(站点地址和WordPress地址)可以通过以下步骤完成:登录WordPress后台:打开WordPress网站的后台管理页面,输入用户名和密码登录。进入设置:在后台左侧菜单中,点击“设置”>“常规”。修改网站地址:在“WordPress地址(URL)”和“站点地址(URL)”字段中......
  • 树形 dp / 换根 dp 入门小记
    背景4.14打abc的时候一眼e题是换根模板,但是我不会,于是就来补档了。什么是树形dp/换根dp一种在树上的dp,一般用dfs进行状态转移。树形dp一般用儿子来更新父亲的答案。换根dp一般在第二次dfs时用父亲的答案转移到儿子去。引入经典树形dp例题:没有上司的舞......
  • 【某NOIP模拟赛T2 - 旅游】--线段树优化 DP 的魅力
    题意:数轴上在起点\(s\)和终点\(t\)间的整点中有\(n\)个关键点,第\(i\)个关键点位置为\(c_i\),可获得\(m_i\)的价值。你可以从起点开始,每次跳至多\(z\)个点(跨过中间的点),而每到达一个\(s\)以外的点需要支付\(a\)的代价,求走到终点的最大价值。\(0\les\lec_i\let......
  • L9613/L9637国产替方案DP9637电摩汽车K总线收发控制器
    DP9637支持ISO9141协议与L9613和L9637兼容,只需要修改电路和控制信号时序逻辑有参考资料,欢迎咨询DP9637是一款应用于汽车诊断系统中的单片总线收发器,为汽车诊断系统提供双向串行通信。该收发器既能工作在发射模式,也能工作在接收模式,并且它具有过温、短路检测功能。芯片采用了......
  • 【排列】(笛卡尔树上 dp?)
    比赛在这B.排列前言:笛卡尔树上dp?这名字很妙啊,但其实不需要笛卡尔树,只不过利用了笛卡尔树的定义一个性质:我们设一个区间\([l,r]\)中的最大值的位置为\(pos\),发现可以把该区间分为\([l,pos]\)和\([pos,r]\)两个子区间,并且这两部分互不影响,就是别管我左边怎么放数,不会对......
  • P6879 [JOI 2020 Final] スタンプラリー 3 [区间DP]
    P6879[JOI2020Final]スタンプラリー3Solution首先这是一道最优值问题,再根据数据范围\(n\le200\),那么正解可能会是\(O(n^3)\)的DP。根据题意,我们发现主角走过的雕像一定是个区间,可以考虑区间DP。想一想我们需要知道什么,然后把它放到DP状态里面。我们需要知道......
  • SSM动漫论坛系统-计算机毕业设计源码52529
    目录1绪论1.1研究背景和意义1.2国内外研究现状1.3论文结构与章节安排1.4SSM框架介绍2 系统分析2.1可行性分析2.1.1技术可行性分析2.1.2经济可行性分析2.1.3操作可行性分析2.2系统功能分析2.2.1功能性分析2.2.2非功能性分析2.3 系统用例分......
  • LeetCode:3259. 超级饮料的最大强化能量(DP Java)
    目录3259.超级饮料的最大强化能量题目描述:实现代码与解析:DP原理思路:3259.超级饮料的最大强化能量题目描述:        来自未来的体育科学家给你两个整数数组 energyDrinkA 和 energyDrinkB,数组长度都等于 n。这两个数组分别代表A、B两种不同能量饮料每......