题解：线性DP

首先，我们考虑计算选择前$n$个数字的最大和。

我们按照动态规划的三要素来分析这道题：状态方程定义、状态初始化、状态转移方程

状态方程定义

定义$f[i]$表示选择前$i$个数字的最大和

状态初始化

本题的下标从0开始

$f[0]=a[0]$

$f[1]=max(a[0],a[1])$

状态转移方程

• 如果选择第$i$个数字，由于不能选择相邻的数字，因此不能选择第$i-1$个数字，对应的答案为$f[i-2]+a[i]$
• 如果不选择第$i$个数字，对应的答案为$f[i-1]$

本题不仅需要求解最大和，还需要提输出选择的每个数字，这其实就是动态规划最常见的求具体方案的问题。

我们可以把动态规划理解为第三章的搜索与图论，使用状态转移方程进行转移，其实就是相当于图论中从起点出发寻找一个最优解，$f[0]$相当于起点，$f[n-1]$相当于终点，状态转移方程相当于图论中的边。因此，求具体方案其实就是找从起点出发到达终点的路径。

我们从起点考虑不是很方便，因此我们可以从终点考虑，从终点根据状态转移方程反推起点即可。

C++

#include <bits/stdc++.h>
using namespace std;
const int N=1E5+10;
int n,a[N],f[N];
int main()
{
    int x;
    while(cin>>x){
        a[++n]=x;
    }
    f[1]=a[1];
    for(int i=2;i<=n;i++){
        f[i]=max(f[i-1],f[i-2]+a[i]);
    }
    int m=n;
    vector<int>choose;  //选择的下标编号
    while(m>0){
        if(f[m-1]==f[m]){  //没有选择第m个数字
            m--;
        }
        else{
            choose.push_back(m-1);  //下标编号从0开始
            m-=2;
        }
    }
    for(int i=choose.size()-1;i>=0;i--)cout<<choose[i]<<" ";
    puts("");
    cout<<f[n]<<endl;
    return 0;
}

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<Integer> a = new ArrayList<>();
        a.add(0);  // 为了让下标从1开始，我们在数组的开始添加一个0
        while (scanner.hasNextInt()) {
            a.add(scanner.nextInt());
        }
        int n = a.size() - 1;
        int[] f = new int[n + 1];
        f[1] = a.get(1);
        for (int i = 2; i <= n; i++) {
            f[i] = Math.max(f[i - 1], f[i - 2] + a.get(i));
        }
        int m = n;
        List<Integer> choose = new ArrayList<>();  // 选择的下标编号
        while (m > 0) {
            if (f[m - 1] == f[m]) {  // 没有选择第m个数字
                m--;
            } else {
                choose.add(m - 1);  // 下标编号从0开始
                m -= 2;
            }
        }
        Collections.reverse(choose);  // 反转数组，使得输出的顺序正确
        for (int i : choose) {
            System.out.print(i + " ");
        }
        System.out.println();
        System.out.println(f[n]);
    }
}

Python

a = [0]+list(map(int,input().split()))  # 为了让下标从1开始，我们在数组的开始添加一个0
n = len(a)-1
f = [0] * (n + 1)
f[1] = a[1]
for i in range(2, n + 1):
    f[i] = max(f[i - 1], f[i - 2] + a[i])
m = n
choose = []  # 选择的下标编号
while m > 0:
    if f[m - 1] == f[m]:  # 没有选择第m个数字
        m -= 1
    else:
        choose.append(m - 1)  # 下标编号从0开始
        m -= 2
choose.reverse()  # 反转数组，使得输出的顺序正确
for i in choose:
    print(i, end=' ')
print()
print(f[n])