【tyvj1617/2062】偷葡萄(grape)

2014年5月25日1,2080

描述 Description

fox来到了一排葡萄架下,葡萄架上有很多葡萄(n串),它想将一部分葡萄偷走.
每串葡萄都有一个价值,当然,由于有酸有甜,葡萄的价值可能为正,也可能为负.
当然,为了让农夫看不出来,fox规定,每k串葡萄中,它最多选b串,但是由于fox是比较贪心的,每连续k串葡萄中,它会最少选a串
例如n=5 k=3 a=1 b=2时,在第1–第3串葡萄中,fox只能选1或2串,在第2–第4串葡萄中,fox也只能选1或2串.
图1的选法是不合法的,因为2–4中选出了3串葡萄
图2的选法也是不合法的,因为1–3中选出了0串葡萄
而图3的选法是合法的.
现在,fox要选出一些葡萄,而农夫得到剩余的葡萄,由于fox有嫉妒心理,希望让fox得到的价值减去农夫得到的价值的差值最大

输入格式 InputFormat

第一行整数n,k,a,b
第二行n个整数表示每串葡萄的价值

输出格式 OutputFormat

仅一行,表示答案

样例输入 SampleInput [复制数据]

样例输出 SampleOutput [复制数据]

数据范围和注释 Hint

对于10%的数据         n<=10
对于另外30%的数据     a=0,b=k
对于100%数据       n<=10000,0<=a<=b<=k<=10

来源 Source

来源:fox_pro    开学欢乐赛

题解
状压dp,预处理出可行状态,然后转移
我的做法是从前往后转移,并且每次删掉状态第1位,分类讨论状态第K位
注意ans初始值要设为-inf