#P4852. yyf hates choukapai

    ID: 3793 Type: RemoteJudge 912ms 256MiB Tried: 0 Accepted: 0 Difficulty: 6 Uploaded By: Tags>动态规划,dp2018单调队列洛谷原创Special Judge前缀和期望队列

yyf hates choukapai

题目背景

非酋 yyf 总是抽不到自己想要的卡,因此还十分讨厌抽卡。但玩 sif 不可能不抽卡,于是他去请教了一下欧皇 dew。dew 告诉了他关于抽卡的秘密,然而 yyf 还是不知道如何让自己欧气尽量地大,于是他找到了你。

题目描述

dew 告诉 yyf,人在抽每张卡时欧气值都是固定的,第 ii 张卡的欧气值为 aia_i,而在连抽时,欧气值等于第一张卡的欧气值。

“每次抽卡的欧气之和”指每次单抽的欧气之和加上每次连抽的欧气之和,一次连抽的欧气不加权,只计算一次。

yyf 想 cc 连抽(连续抽 cc 张卡)nn 次,单抽 mm 次,因为一直单抽太累,yyf 不想连续单抽超过 dd 次(可以连续单抽恰好 dd 次)。共有 c×n+mc\times n+m 张卡,抽卡的顺序不能改变,每张卡都必须且只能抽一次,只能改变哪几张卡连抽、哪几张卡单抽。那么 yyf 每次抽卡的欧气之和最多能达到多少,又如何实现呢?

输入格式

1144 个正整数 n,m,c,dn,m,c,d

22c×n+mc\times n+m 个正整数,其中第 ii 个正整数 aia_i 代表第 ii 张卡的欧气值。

输出格式

11 行一个正整数代表 yyf 每次抽卡的欧气之和的最大值。

22nn 个正整数代表每次连抽的第一张卡的编号,如果有多种方案满足要求任意输出一种(如果不会输出方案也请在第二行随意输出 nn 个整数,否则可能 00 分)。

方案请升序输出。

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

提示

20%20\% 的数据有 1n51 \le n \le 51m51 \le m \le 52c52 \le c \le 5

50%50\% 的数据有 1n401 \le n \le 401m2001 \le m \le 2002c202 \le c \le 20

另有 20%20\% 的数据有 d=md=m

100%100\% 的数据有 1n401 \le n \le 401m800001 \le m \le 800002c30002 \le c \le 30001ai100001 \le a_i \le 100001dm1 \le d \le md×(n+1)md\times (n+1) \ge m

1010 个测试点,每个测试点答案错误 00 分,答案正确方案错误 66 分,答案正确方案正确 1010 分。

样例解释:输出的方案就是样例解释了 QAQ。

样例一:单抽 11,连抽 242\sim 4,连抽 575\sim 7,单抽 88,连抽 9119\sim 11,单抽 1212,欧气值总和为 2+7+5+8+5+9=362+7+5+8+5+9=36

样例二:单抽 11,连抽 232\sim 3,单抽 44,单抽 55,连抽 676\sim 7,单抽 88,单抽 99,欧气值总和为 7+3+7+7+5+10+2=417+3+7+7+5+10+2=41

可以证明在满足条件的情况下上述两种方案是欧气值总和最大的。