XIX Open Cup Grand Prix of Korea K.Interesting Drug @ Wings            分类 ACM
发布于 星期一, 二月 1 日, 2021 年
更新于 星期二, 七月 20 日, 2021 年

题目

题意

一条路上按顺序有 $n$ 瓶毒药, 对于每个 $i \in [1, n]$, 求出如下的值: 从i出发, 每个时刻都可以向左或向右, 最终可以得到一个吃毒药的排列$P$, 一个排列的伤害定义为$\sum_{j=1}^n D_j \cdot [P_{C_j} = j]$, 求可能的排列中最大的伤害值. $C$和$D$给出.

$2 \le n \le 3 \cdot 10^5$

题解

区间DP显然.

不过这里的状态定义和平常不太一样. 因为要算从每个点走完所有的值, 如果从小区间推到大区间的话, 就要枚举起点, 复杂度$O(n^3)$, 怎么都压不下来.

设$dp(i, j)$为已经走完了区间$[i, j]$, 走完剩下的所有点还需要的最大花费. 转移从大区间推到小区间, 答案就是$dp(i, i) + D_i \cdot [C_i = 1]$.

方程很容易推得:

$$dp(i, j) = max \{ dp(i-1, j) + D_i \cdot [C_{i-1} = j-i+2], dp(i, j+1) + D_j \cdot [C_{j+1} = j-i+2] \}$$

这样复杂度是$O(n^2)$的.

注意到, 对于一个$i$, 最多只可能有种区间的转移会加上$D_i$. 这很好理解, 比如$D_3 = 3$, 那么只有区间$[1, 2]$到$[1, 3]$和$[4, 5]$到$[3, 5]$的这两个走法对应的转移会产生额外的贡献$D_i$, 而其他走到$3$这个点都没有额外的贡献.

如果我们把他放到图上来看, 就会是类似这样的东西:

图

上图是样例. 相当于要求一个从$(1, n)$走到$(i, i)$的最长路(当然最后答案要加上$D_i \cdot [C_i = 1]$). 图中写了数字的边是转移方程中对应的$D_i$, 没有的表示这个转移不加$D_i$.

综上, 最多只会有$2n$条有权值的边, 而没有权值的边, 就直接从下面和右边转移.

于是我们可以根据这个性质进行优化.

考虑维护一颗线段树, 一开始表示第1行的值. 先找当前行横着的有权值的边, 那么这条边左边的点都有可能从这里转移, 所以我们把左边的这个区间每一个点对$dp(i, j) + w$取max, 就得到了所有点的dp值. 如果有两条横着的边, 要注意一下操作的顺序, 要从右往左做, 因为左边的dp值会被右边的更新.

做完一行, 我们就可以轻松单点查询得到一个$(i, i)$的答案了.

然后向上推, 由于竖着的边有权值的可能很少, 所以先假定边权都是0, 那么就是直接对应列相等的点直接转移, 表现在线段树上就是叶子节点的权值不变.

然后考虑有边权的竖直边. 同样是某个点的值可以影响左边区间的值, 如图:

区间更新

这样就刚好对应了从下面和右边两个点取max.

这个做法就很奇妙……

复杂度$O(n\log n)$

代码
const int MAXN = 3e5+10;

int n, c[MAXN], d[MAXN];
VI r[MAXN];

struct Node {
	int l, r, mid;
	LL val, tag;
} tree[MAXN << 2];

void push_up(int u) {
	tree[u].val = max(tree[LCH(u)].val, tree[RCH(u)].val);
}

void build(int l, int r, int u) {
	tree[u] = {l, r, (l + r) >> 1, 0, 0};
	if (l < r) {
		build(l, tree[u].mid, LCH(u));
		build(tree[u].mid + 1, r, RCH(u));
		push_up(u);
	}
}

void update_node(int u, LL x) {
	tree[u].val = max(tree[u].val, x);
	tree[u].tag = max(tree[u].tag, x);
}

void push_down(int u) {
	update_node(LCH(u), tree[u].tag);
	update_node(RCH(u), tree[u].tag);
	tree[u].tag = 0;
}

void update(int l, int r, LL x, int u = 1) {
	if (tree[u].l == l && tree[u].r == r)
		update_node(u, x);
	else {
		push_down(u);
		if (r <= tree[u].mid)
			update(l, r, x, LCH(u));
		else if (l > tree[u].mid)
			update(l, r, x, RCH(u));
		else {
			update(l, tree[u].mid, x, LCH(u));
			update(tree[u].mid + 1, r, x, RCH(u));
		}
		push_up(u);
	}
}

LL query(int l, int r, int u = 1) {
	if (tree[u].l == l && tree[u].r == r)
		return tree[u].val;
	else {
		push_down(u);
		if (r <= tree[u].mid)
			return query(l, r, LCH(u));
		else if (l > tree[u].mid)
			return query(l, r, RCH(u));
		else
			return max(query(l, tree[u].mid, LCH(u)), query(tree[u].mid + 1, r, RCH(u)));
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", c + i);
	for (int i = 1; i <= n; i++)
		scanf("%d", d + i);
	for (int i = 1; i <= n; i++)
		if (c[i] > 1 && i - c[i] + 1 <= n)
			r[i - c[i] + 1].push_back(i);
	build(1, n, 1);
	for (int i = 1; i <= n; i++) {
		for (int j = r[i].size() - 1; ~j; j--) {
			int p = r[i][j];
			update(1, p-1, query(p, n) + d[p]);
		}
		printf("%lld%c", query(i, n) + (c[i]==1) * d[i], " \n"[i == n]);
		int j = c[i] + i - 1;
		if (j <= n)
			update(1, j, query(j, n) + d[i]);
	}
	return 0;
}
留下昵称和邮箱, 可在第一时间获悉回复通知哦~

2021 FLAG

  • 找个妹子
  • 进计科
  • XCPC拿块金牌
  • 补全算法知识, 整全板子
  • 学会Web开发相关知识
  • 在服务器上搭建电子书库
  • 写个游戏并上线
  • 能弹一首曲子
  • 写首完整的曲子
  • 练习悠悠球
  • 三阶速拧20s

个人简介

我叫 Wings, 来自江西上饶, 目前人在西安, 是西电的一名学生.

常以 WingsWingsZengWingsWings的ID在各大小网站上游走, 一般来说, Wings不是我 😔, WingsZeng 一定是我 😊.

热爱算法, 喜欢钻研各种计算机技术.

业余爱好广泛, 只要不是文化课基本上都感兴趣😏.

开发/项目经历

  1. Android游戏 小墨滴的复仇 (弃坑)
  2. Android游戏 Circle Run (弃坑)
  3. Windows游戏 Snague (可能弃坑了吧)
  4. Python后端 Fathy' (可能弃坑了吧)

to be continued

教育经历

时间 学历 学校
2008-2014 小学 上饶市第十二小学
2014-2017 初中 上饶市第四中学
2017-2020 高中 上饶市第一中学
2020-2024 本科 西安电子科技大学
to be continued

比赛/竞赛经历

太久远太小的记不到了…

  1. 2017 国学竞赛初赛江西 没有分数或排名 二乙
  2. 2018 NOIP提高 258 省二
  3. 2019 CSP-S江西专场 145 省二
  4. 2019 数学竞赛初赛 70 没排名 (复赛打铁qaq)
  5. 2020 Gitee|Python贪吃蛇魔改大赛 可能是第四? 二等奖
  6. 2020 西电ACM训练基地熊猫杯 第四 银牌
  7. 2020 西安三校微软学生俱乐部Hackathon 和二等奖最后一名差0.5分 三等奖
  8. 2020 西电星火杯 三等奖
  9. 2020 西电ACM新生赛 第九 金牌
  10. 2020 ICPC 亚洲区域赛 济南站 132名 铜牌
  11. 2020-2021 第二届全国大学生算法设计与编程挑战赛(冬季赛) 924名 铜牌 (别骂了别骂了)
  12. 2020 ICPC 亚洲区域赛 昆明站 打星
  13. 2020 ICPC Asia-East Continent Final 签完到溜 打铁
  14. 西电"智能星"第一届自动驾驶小车比赛 第五 优胜奖|极速奖 本来可以冠军的别骂了别骂了

to be continued

爱好

技术

  • 算法
  • 独立游戏开发

游戏

  • Minecraft
  • Black Survival
  • I Wanna
  • Celeste
  • Life is Strange
  • Need for speed

运动

  • 篮球
  • 桌球
  • 乒乓球
  • 羽毛球
  • 慢跑

音乐

  • 吉他
  • 词曲
  • 流行

玩具

  • 魔方
    • 三阶速拧
    • 三阶盲拧
    • 高阶
  • yoyo球

追星

  • VAE
  • Benedict Cumberbatch