题解 | #大富翁游戏#

import java.util.Scanner;
import java.util.ArrayList;

public class Main{
    public static void main(String[] args){
        //读取数据
        Scanner in = new Scanner(System.in);
        int M = in.nextInt();
        ArrayList<Integer> items = new ArrayList<Integer>();
        while(in.hasNext()){
            items.add(in.nextInt());
        }
        Integer[] input = items.toArray(new Integer[0]);

        //基本情况
        if(M <2 || input.length==0) {System.out.println(M); return;}
        //初始化 多一个方便处理
        int [] dp = new int[input.length+1];
        dp[0] = M;
        int max = 0;
        //动态规划，如果能量不足 就不能继续更新了
        for(int i = 1;  i<= input.length;i++){
            if(dp[i-1] >=2) 
                dp[i] = dp[i-1]-2 + input[i-1];       
            if(i>=2 && dp[i-2] >=3) 
                dp[i] = Math.max(dp[i],dp[i-2] - 3 + input[i-1]);
            max = Math.max(dp[i],max);
        }
        System.out.println(max);
    }
}