bzoj - 4842

Posted by WildCow on September 29, 2018

[Neerc2016]Delight for a Cat

Time Limit: 10MS
Memory Limit: 128 MB

Description

ls 是一个特别堕落的小朋友,对于 $n$ 个连续的小时,他将要么睡觉要么打隔膜,一个小时内他不能既睡觉也打隔膜,因此一个小时内他只能选择睡觉或者打隔膜,当然他也必须选择睡觉或打隔膜,对于每一个小时,他选择睡觉或打隔膜的愉悦值是不同的,对于第 $i$ 个小时,睡觉的愉悦值为 $s_i$,打隔膜的愉悦值为 $e_i$,同时又有一个奥妙重重的规定:对于任意一段连续的 $k$ 小时,ls 必须至少有 $t_1$ 时间在睡觉,$t_2$ 时间在打隔膜。那么ls想让他获得的愉悦值尽量大,他该如何选择呢?

Input

第一行四个整数, $n, k(1<=k<=n<=1000),t_1,t_2(0<=t1,t2<=k;t1+t2<=k)$,含义如上所述。 接下来一行 $n$ 个整数,第 $i$ 个整数 $s_i(0<=s_i<=1e^9)$ 表示睡觉的愉悦值。 接下来一行 $n$ 个整数,第 $i$ 个整数 $ei(0<=e_i<=1e^9)$ 表示打隔膜的愉悦值。

Output

第一行输出最大的愉悦值。

接下来一行输出一个长度为 $n$ 的字符串

第 $i$ 个字符为 $E$ 则代表第 $i$ 小时在打隔膜,第 $i$ 个字符为 $S$ 则代表第 $i$ 个小时在睡觉。

Sample Input

10 4 1 2
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1

Sample Output

69
EEESESEESS


是一道不错的题
先考虑怎么处理 $t_1$ 和 $t_2$ 的两个约束条件
我们先让他全程打游戏(隔膜应该是游戏?)
那么我们现在变成决策他到底要哪一天能睡觉
假如他第 $i$ 天睡觉
那么对代价的贡献是 $s_i - e_i$
我们对于任意一个长度为 $k$ 的区间
设 $dp_i = 1$ 为睡觉
$dp_i = 0$ 为打游戏
那么我们显然有 $t_1≤ \sum_i^{i + k - 1}dp_i ≤ k - t_2$
这样我们就能把 $t_1$ 和 $t_2$ 的限制就只和一个变量有关了
然后我们想最大化 $\sum dp_i * (s_i - e_i)$
按照志愿者招募的老套路
我们增加两个变量 $x, y$ 让等式平衡
即 $t_1 + x_i = \sum_i^{i + k - 1}dp_i = k - t_2 - y_i$ 让我们把所有式子都列出来,然后前面后面都补上 0 = 0
需要注意一点变量 $dp$ 的范围只有 0 和 1

差分一下我们有

我们会发现每个变量会出现两次
分别在两个不同等式的左边和右边
然后根据差分的构造性质
带上符号
出现的所有常量的和为 0
现在是脸上写着网络流
我们把每个等式看成一个点
等号在描述这个点的流量平衡
等式左边的变量可以当作流往这个点的流量,常数当作源点流向这个点的流量
等式右边的变量可以当作这个点流出的流量,常数当作这个点流向汇点的流量
那么建图自然而然就来了
对于一个变量出现在第 $i$ 个式子的右边,出现在第 $j$ 个式子的左边
那么我们从 $i$ 往 $j$ 连边
如果是变量 $dp$
流量为 1
否则流量为 $inf$
对于一个常数出现在第 $i$ 个式子的左边
我们从源点往 $i$ 连边,流量为那个常数
对于一个常数出现在第 $i$ 个式子的右边
我们从 $i$ 往汇点连边,流量为那个常数
因为常数带上符号的和为 $0$
且其它边的容量都是 $inf$
所以能保证容量非 $inf$ 的边正好满流
这样就是一个流量平衡
再回到题目,我们想最大化 $\sum dp_i * (s_i - e_i)$
那我们把所有根据 $dp_i$ 连的边加上 $s_i - e_i$ 的费用
其余的费用为 0
跑费用流就好了
然后再暴力 chekc 所有 $dp$ 连的边看看是 0 还是 1

代码咕掉了