首页 > 其他分享 >CF2019 F. Max Plus Min Plus Size

CF2019 F. Max Plus Min Plus Size

时间:2024-10-03 08:51:38浏览次数:8  
标签:Min int Max pos Plus vec Size

ddp题解,就是 \(f[pos][o][l][r]\) 表示线段树上pos位置的区间是否选出最大值,以及左右端点有没有被去到时的最大值。然后用线段树维护依次取某个值为最小值的时候dp的最优解。

const int N = 2e5 + 5;
int T, n, a[N], f[N << 2][2][2][2];
inline int getmax(int pos) { return max(max(f[pos][1][0][0], f[pos][1][1][0]), max(f[pos][1][1][1], f[pos][1][0][1])); }
inline void update(int pos, int idx) {
	for (int i = 0; i < 2; i++)
	for (int j = 0; j < 2; j++)
	for (int k = 0; k < 2; k++) f[pos][i][j][k] = -1e9;
	f[pos][0][0][0] = 0;
	if (a[idx] < 0) return;
	f[pos][0][1][1] = 1;
	f[pos][1][1][1] = a[idx] + 1;
}

inline void pushup(int pos) {
	for (int i = 0; i < 2; i++)
	for (int j = 0; j < 2; j++)
	for (int k = 0; k < 2; k++) f[pos][i][j][k] = -1e9;
	
	for (int a = 0; a < 2; a++)
	for (int b = 0; a + b < 2; b++)
	for (int i = 0; i < 2; i++)
	for (int j = 0; j < 2; j++)
	for (int x = 0; x + j < 2; x++)
	for (int y = 0; y < 2; y++)
		chkmax(f[pos][a + b][i][y], f[pos << 1][a][i][j] + f[pos << 1 | 1][b][x][y]);
}

inline void build(int pos, int l, int r) {
	if (l == r) { update(pos, l); return; }
	int mid = l + r >> 1;
	build(pos << 1, l, mid);
	build(pos << 1 | 1, mid + 1, r);
	pushup(pos);
}

inline void modify(int pos, int l, int r, int x) {
	if (l == r) { update(pos, l); return; }
	int mid = l + r >> 1;
	if (x <= mid) modify(pos << 1, l, mid, x);
	else modify(pos << 1 | 1, mid + 1, r, x);
	pushup(pos);
}

vector <pii> vec;

signed main(void) {
	for (read(T); T; T--) {
		read(n); vec.clear();
		for (int i = 1; i <= n; i++)
			read(a[i]), vec.push_back(Mp(a[i], i));
		build(1, 1, n); sort(vec.begin(), vec.end());
		int ret = 0;
		for (auto u : vec) {
			int x = u.first, y = u.second;
			chkmax(ret, x + getmax(1));
			a[y] = -1;
			modify(1, 1, n, y);
		}
		writeln(ret);
	}
	//fwrite(pf, 1, o1 - pf, stdout);
	return 0;
}

标签:Min,int,Max,pos,Plus,vec,Size
From: https://www.cnblogs.com/EternalEpic/p/18445362

相关文章

  • 七,MyBatis-Plus 扩展功能:乐观锁,代码生成器,执行SQL分析打印(实操详细使用)
    七,MyBatis-Plus扩展功能:乐观锁,代码生成器,执行SQL分析打印(实操详细使用)@目录七,MyBatis-Plus扩展功能:乐观锁,代码生成器,执行SQL分析打印(实操详细使用)1.乐观锁2.代码生成器3.执行SQL分析打印4.总结:5.最后:1.乐观锁首先我们需要先了解开发中的一个常见场景,叫做并发请求。并......
  • 长江存储致态TiPlus7100 4TB满盘读写测试:性能几乎没有下降
    一、前言:看看满盘状态下致态TiPlus71004TB性能会如何!现在还有很多同学对于长江存储品牌的存储产品不太信任,在选择SSD时会优先考虑三星、西数这样的品牌。有鉴于此,我们此次会将手上的长江存储致态TiPlus71004TBSSD进行更严苛测试,将SSD填入80%的数据,也就是在近乎满盘的状态下,看......
  • MyBatis-plus 3.5之前版本 处理存储json数据
    MyBatis-plus3.6之后支持集合泛型,不需要自定义TypeHandler当前使用的是MyBatis-plus3.5.2版本一:如果是支持对象,直接用MP内置的Handler,JacksonTypeHandler或FastjsonTypeHandler@TableField(typeHandler=FastjsonTypeHandler.class)//@TableField(typeHandler=JacksonTypeHa......
  • sizeof vs strlen - 关于代码可读性、性能考量和编译器优化
    1、起因经常在咱们代码里面见到sizeof(“HEADER”)这类代码来计算常量字符串的长度,例如上次的一个代码review:之所以这么写可能基于以下几点考虑:(1)sizeof()是运算符而不是函数调用,编译时确定而不是运行时执行,因此不占用运行时时间(2)strlen()是GLIBC标准库函数,运行时需要进行......
  • 五,MyBatis-Plus 当中的 “ActiveRecord模式”和“SimpleQuery工具类”(详细实操)
    五,MyBatis-Plus当中的“ActiveRecord模式”和“SimpleQuery工具类”(详细实操)文章目录五,MyBatis-Plus当中的“ActiveRecord模式”和“SimpleQuery工具类”(详细实操)1.ActiveRecord模式2.ActiveRecord介绍2.1ActiveRecord实现3.SimpleQuery工具类3.1SimpleQuer......
  • 五,MyBatis-Plus 当中的 “ActiveRecord模式”和“SimpleQuery工具类”(详细实操)
    五,MyBatis-Plus当中的“ActiveRecord模式”和“SimpleQuery工具类”(详细实操)@目录五,MyBatis-Plus当中的“ActiveRecord模式”和“SimpleQuery工具类”(详细实操)1.ActiveRecord模式2.ActiveRecord介绍2.1ActiveRecord实现3.SimpleQuery工具类3.1SimpleQuery介绍3.2list......
  • 【漏洞复现】用友畅捷通-TPlus FileUploadHandler.ashx 任意文件上传
    》》》产品描述《《《  ‌用友畅捷通-TPlus‌是由用友集团成员企业畅捷通公司开发的一款企业级财务管理工具,旨在帮助企业实现财务管理的现代化和智能化。作为畅捷通旗下的核心产品,TPlus集成了财务核算、资金管理、预算控制等多项核心功能,通过自动化和智能化的手段,提高企......
  • 从魔兽世界和3dmax中看“安全代码”设计
    魔兽世界在魔兽世界中,可以通过插件来增强游戏界面,官方同样通过lua调用接口来实现游戏的操作界面。在游戏的提供的接口中,大致分安全函数和普通函数。普通函数允许官方调用和用户调用,安全函数则只允许官方调用或对游戏平衡等影响不大的情况下调用那我猜测他应该是怎么做的?在魔......
  • SpringBoot-MybatisPlus项目中,在控制台查看sql执行日志的方法
    SpringBoot-MybatisPlus项目中,在控制台查看sql执行日志的方法springboot、maven、mybatisplus、sql、日志、控制台、console、log背景在baomidou.com学习mybatisPlus入门的过程中,接触到表名和关键词冲突,加注解加表名引号后问题解决。不过我还想,在控制台打印一下执行......
  • Himax 10.36寸 incell触摸调试
    触摸是带笔的,数据比较大,用的是spi接口。 一、添加驱动:drivers/input/touchscreen/hxchipset 二、dts配置&spi4{status="okay";pinctrl-0=<&spi4m1_cs0&spi4m1_cs1&spi4m1_pins>;himax_touch@0{compatible="hima......