P6837

题目内题解

此为出题人题解:

此题是线性dp的一道典题.

注意数据范围 经过了大幅增强且不存在水数据的情况(我不到啊 用数据生成器的话改数据范围挺容易的)

注意到数据范围:

$n \le 1e7$

需要开启关闭同步流.

在这里提供一份关闭同步流的模板代码:

ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

这段代码放在 $main$ 函数开头即可成功的关闭同步流.

同样的 需要开启long long 不然在大数据下int会溢出导致WA

但是......开启了long long再开数组 你们会发现一个事情:MLE了

是的没错 因为long long 和int的内存消耗不同 所以会导致MLE的诞生

但也并不是没有办法.

本题的状态转移方程有一个关键点 即在这一天可获得的最大快乐值只跟前一天可获得的最大快乐值有关系.

所以我们可以只开6个变量

分别表示 当前天选择做1 2 3事件时可获得的最大快乐值和前一天选择做1 2 3 事件时可获得的最大快乐值.

我们分别记为$a_1,b_1,c_1,a_2,b_2,c_2$.

注意到题面的限制:连续两天不可以选择同样的两件事去做 所以我们在转移时 每个天不可以加上前一天相同的事件可得的最大快乐值

当然 描述肯定是不够的 变量a的转移方程如下:

$a_1=max(b_2,c_2)$+当前天选择a事件可以获得的快乐值

剩下的自己举一反三吧.