【vijos1891】学姐的逛街计划

2014年10月25日2,2170

描述

doc 最近太忙了, 每天都有课. 这不怕, doc 可以请假不去上课.
偏偏学校又有规定, 任意连续 n 天中, 不得请假超过 k 天.

doc 很忧伤, 因为他还要陪学姐去逛街呢.

后来, doc发现, 如果自己哪一天智商更高一些, 陪学姐逛街会得到更多的好感度.
现在 doc 决定做一个实验来验证自己的猜想, 他拜托 小岛 预测出了 自己 未来 3n 天中, 每一天的智商.
doc 希望在之后的 3n 天中选出一些日子来陪学姐逛街, 要求在不违反校规的情况下, 陪学姐逛街的日子自己智商的总和最大.

可是, 究竟这个和最大能是多少呢?

格式

输入格式

第一行给出两个整数, n 和 k, 表示我们需要设计之后 3n 天的逛街计划, 且任意连续 n 天中不能请假超过 k 天.
第二行给出 3n 个整数, 依次表示 doc 每一天的智商有多少. 所有数据均为64位无符号整数

输出格式

输出只有一个整数, 表示可以取到的最大智商和.

样例1

样例输入1

样例输出1

限制

对于 20% 的数据, 1 <= n <= 12 , k = 3.
对于 70% 的数据, 1 <= n <= 40 .
对于 100% 的数据, 1 <= n <= 200 , 1 <= k <= 10.

题解

设a[i]为第i天是否去逛街,v[i]为第i天智商

对于第i个不等式,添加辅助变量y[i]

设p[i]=a[i]+a[i+1]+…a[i+n-1]

a[1]+a[2]+…+a[n]+y[1]=k

a[2]+a[3]+…+a[n+1]+y[2]=k

a[2n+1]+a[2n+2]+…+a[3n]+y[2n+1]=k

ans=max{∑ a[i]*v[i]}

将相邻两式相减

a[1]+a[2]+…+a[n]+y[1]=k  ———> 1

y[1]+a[1]=a[n+1]+y[2]  ———> 2

y[2]+a[2]=a[n+2]+y[3]  ———> 3

y[n+1]+a[n+1]=a[2n+1]+y[n+1]  ———> n+1

y[2n]+a[2n]=a[3n]+y[2n+1]  ———> 2n

a[2n+1]+a[2n+2]+…+a[3n]+y[2n+1]=k  ———> 2n+1

然后把等式当做点,变量当做边

等号左右两边为流出/流入流量

最大费用最大流。。。