← 返回比赛
已结束 GESP巅峰赛#32
← 上一题 下一题 →

A7303 | 星灯选址

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

雾港学宫要在一条直线上布置星灯。共有 $n$ 个候选位置，按从左到右编号为 $1\sim n$，在位置 $i$ 布置星灯会获得收益 $a_i$（可为负）。

为了避免相互干扰，规定：

- 不能在相邻的两个位置同时布置星灯（即不能同时选 $i$ 与 $i+1$）。

请你选择若干位置使总收益最大，并输出最大总收益以及一种方案。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。

输出格式

第一行输出最大总收益 $S$。

第二行输出选中位置的个数 $k$。

第三行输出 $k$ 个严格递增的下标（用空格分隔）。若 $k=0$，第三行输出空行即可。

输入输出样例

输入 #1
6
5 -2 4 1 -10 6
输出 #1
15
3
1 3 6
C++ 编辑器
输入
输出