小美和大富翁

import java.io.*;
public class Main {
    public static final int MAXN=100001;
    public static long[][][] dp=new long[MAXN][16][2];
    public static long[][] dp1=new long[MAXN][16];
    public static int[] array=new int[MAXN];
    public static int n;
    //记忆化收索
    public static long dfs(int cur,int status,long worth){
        if(cur>n) return Integer.MIN_VALUE;
        if(cur==n&&worth+array[cur]>=0) return array[cur];
        if(worth+array[cur]<0) return Integer.MIN_VALUE;
        if(status==0) status=15;
        if(dp[cur][status][0]!=-2&&dp[cur][status][1]>=worth) return dp[cur][status][0];
        long ans=Integer.MIN_VALUE;
        ArrayList<Integer> list=new ArrayList<>();
        for(int i=0;i<4;i++){
            if((status&(1<<i))!=0){
                if(array[cur+i+1]>=0) ans=Math.max(ans,dfs(cur+i+1,(status^(1<<i)),worth+array[cur]));
                else list.add(i);
            }
        }
        for(int i:list){
            ans=Math.max(ans,dfs(cur+i+1,(status^(1<<i)),worth+array[cur]));
        }
        list.clear();
        dp[cur][status][0]=ans==Integer.MIN_VALUE?Integer.MIN_VALUE:ans+array[cur];
        dp[cur][status][1]=worth;
        return dp[cur][status][0];
    }
    //动态规划版
    public static void dfs1(){
        for(int i=1;i<=n;i++){
            for(int j=0;j<=15;j++){
                long ans=Integer.MIN_VALUE;
                for(int k=0;k<4;k++){
                    if((j&(1<<k))==0&&i>k){
                        ans=Math.max(ans,dp1[i-k-1][(j|(1<<k))==15?0:(j|(1<<k))]);
                    }
                }
                if(ans+array[i]<0) dp1[i][j]=Integer.MIN_VALUE;
                else dp1[i][j]=ans+array[i];
                //System.out.println(i+" "+j+" "+dp1[i][j]);
            }
        }
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        n=Integer.parseInt(br.readLine());
        String[] str=br.readLine().split(" ");
        array[0]=0;
        for(int i=0;i<n;i++){
            array[i+1]=Integer.parseInt(str[i]);
        }
        for(long[][] P:dp){
            for(long[] P1:P){
                Arrays.fill(P1,-2);
            }
        }
        //dfs(0,15,0);
        dfs1();
        bw.write((dp1[n][0]==Integer.MIN_VALUE?-1:dp1[n][0])+"");
        bw.close();
        br.close();
    }
}

public class BigRichGame {
    public static void main(String[] args) {
        int[] cityCoin = {-1, 2, 3, 4, -9, -9, -1, 3, -1, -1, 10, -1, 20};
        int result = getResult(cityCoin);
        if (result == Integer.MIN_VALUE) {
            System.out.println("没有合适的组合到达n城市");
        } else {
            System.out.println("最大金币值:" + result);
        }
    }


    //将数组拆分成很多个10步
    public static int getResult(int[] cityCoin) {
        int[] steps = {1, 2, 3, 4};
        int res = 0;
        int l = cityCoin.length - 1;
        int r = -1;
        while (r < l) {
            int n = Math.min(r + 10, l);
            LinkedList<Integer> roundStep = new LinkedList<>();
            int max = getGoldCoin(cityCoin, r, n, steps, r, roundStep);
            res += max;
            r += 10;
        }
        return res;
    }


    //每十步的最优解
    public static int getGoldCoin(int[] cityCoin, int r, int n, int[] steps, int start, LinkedList<Integer> roundStep) {
        //如果已经到达n城市则不需要再往前,直接返回我所有拿到的值
        if (r == n) {
            return cityCoin[n];
        }

        int max = Integer.MIN_VALUE;

        for (int step : steps) {
            int next = r + step;

            //如果大于n则直接结束
            if (next > n) {
                continue;
            }

            if (roundStep.contains(step)) {
                continue;
            }

            roundStep.add(step);

            int nextAns = getGoldCoin(cityCoin, next, n, steps, start, roundStep);
            int nowAns = r != start ? cityCoin[r] : 0;
            int ans = nextAns == Integer.MIN_VALUE ? Integer.MIN_VALUE : Math.max(max, nowAns + nextAns);
            max = Math.max(ans, max);
            roundStep.removeLast();
        }

        return max;
    }

}