首页 > 题解 > bzoj 4842 [Neerc2016]Delight for a Cat

bzoj 4842 [Neerc2016]Delight for a Cat

Description

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

Input

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

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

题解

我们先让所有时间都睡觉。。假设有一天吃饭,那么我们换成吃饭的费用就是$e_i - s_i$

如果只有睡觉的限制,那么我们要满足的就是从$i$连到$i+1$的,容量不能超过$t_1$,在$i$连到$i+1$的边都表示这天睡觉,容量$t_1$,费用0。

如果吃饭没有限制,就可以从每个$i$连到$i+K$(不够的话到汇点),容量为1,费用为$e_i−s_i$。

然后求最大费用最大流就好了。

考虑有了吃饭限制,相当于我从$i$到$i+1$的边容量变为$r−l$(上界-下界),就代表我一定要有吃饭的流量。

从$i$到$i+1$画一条纵截线,与其相交并且是$i$到$i+k$这样的边至少有$l$个。

再对源点容量做一下限制即可。


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×