07356. 打家劫舍·作案计划 未做

打家劫舍：$n$ 家店排一排，第 $i$ 家有 $a_i$ 元，不能偷相邻两家。输出最大收益，以及一个达到最大收益的作案方案（按编号从小到大输出偷了哪些店）。若多种方案，输出偷的店数最少的那一种；仍相同输出编号最小的一种。

第一行一个整数 $n$。
第二行 $n$ 个整数 $a_i$。

第一行一个整数：最大收益。
第二行若干个递增整数：偷的店编号，用空格分隔（至少偷一家）。

构造规则：从最后一家往回想——若 $f_{i-2}+a_i>f_{i-1}$，说明最优方案里第 $i$ 家被偷了：收下它，接着考虑第 $i-2$ 家；否则第 $i$ 家不偷，接着考虑第 $i-1$ 家（下标越界时，$f_{-1}$、$f_0$ 都按 $0$ 算）。一路走完，把收下的店按编号从小到大输出即可——这就是本课文章第 15 章「记录决策」的做法：转移时顺手记下来路，最后从终点倒着走回起点。

样例解释：$f=[2,7,11,11,12]$（$f_0=0$）。

• $i=5$：$f_3+a_5=11+1=12>f_4=11$ → 偷第 5 家，跳到 3；
• $i=3$：$f_1+a_3=2+9=11>f_2=7$ → 偷第 3 家，跳到 1；
• $i=1$：$f_{-1}+a_1=0+2=2>f_0=0$ → 偷第 1 家，结束。

收获 $2+9+1=12$，方案 1 3 5，与样例输出一致。

再体会一下「编号最小」的口径：对输入 $a=[5,5,1,5]$，最大收益 $10$ 可由「偷第 1、4 家」或「偷第 2、4 家」达成；按规则从 $i=4$ 收起（$f_2+5=10>f_3=6$），退回第 2 家时 $f_0+5=5$ 并不大于 $f_1=5$（等号处不偷），最终输出 1 4。

$1\le n\le 2000$，$1\le a_i\le 10^4$。