小美和大富翁

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;
    }

}

import sys

def fn(init_curr, numbers):
    l = [[0 for _ in range(4)] for _ in range(10)]
    l[0][0] = numbers[0] + init_curr
    l[1][1] = numbers[1] + init_curr
    l[2][2] = numbers[2] + init_curr
    l[3][3] = numbers[3] + init_curr

    l[2][0] = max(l[0][0], l[1][1]) + numbers[2] if max(l[0][0], l[1][1]) > 0 else -1

    l[3][0] = max(l[0][0], l[2][2]) + numbers[3] if max(l[0][0], l[2][2]) > 0 else -1

    l[4][0] = max(l[0][0], l[3][3]) + numbers[4] if max(l[0][0], l[3][3]) > 0 else -1

    l[4][1] = max(l[1][1], l[2][2]) + numbers[4] if max(l[1][1], l[2][2]) > 0 else -1
    l[5][0] = (
        max(l[4][1], l[3][0], l[2][0]) + numbers[5]
        if max(l[4][1], l[3][0], l[2][0]) > 0
        else -1
    )

    l[5][1] = max(l[1][1], l[3][3]) + numbers[5] if max(l[1][1], l[3][3]) > 0 else -1
    # [[0, 1, 3], [], [2, 3]],
    l[6][0] = (
        max(l[5][1], l[4][0], l[2][0]) + numbers[6]
        if max(l[5][1], l[4][0], l[2][0])
        else -1
    )
    l[6][2] = max(l[2][2], l[3][3]) + numbers[6] if max(l[2][2], l[3][3]) > 0 else -1
    #  [[0, 2, 3]],
    l[7][0] = (
        max(l[6][2], l[4][0], l[3][0]) + numbers[7]
        if max(l[6][2], l[4][0], l[3][0]) > 0
        else -1
    )
    # 1, 2, 3
    l[8][1] = (
        max(l[6][2], l[5][1], l[4][1]) + numbers[8]
        if max(l[6][2], l[5][1], l[4][1]) > 0
        else -1
    )
    l[9][0] = (
        max(l[8][1], l[7][0], l[6][0], l[5][0]) + numbers[9]
        if max(l[8][1], l[7][0], l[6][0], l[5][0]) > 0
        else -1
    )
    return l[9][0]

    # aaa_maps = [[0 for _ in range(4)] for _ in range(10)]


count = int(sys.stdin.readline())
numbers = sys.stdin.readline().split()
numbers = [int(val) for val in numbers]
numbers = numbers + ([0] * (10 - len(numbers) % 10) if len(numbers) % 10 > 0 else [])
lp = len(numbers) // 10
init_curr = 0
for l in range(lp):
    init_curr = fn(init_curr, numbers[l * 10 : l * 10 + 10])
    if init_curr < 0:
        break
print(init_curr if init_curr >= 0 else -1)

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
typedef pair<int,int>PII;
typedef pair<int,__int128>PI;
typedef pair<double,double>PDD;
typedef pair<LL,LL>PLL;
typedef tuple<LL,LL,LL,LL>t4i;
typedef tuple<int,int,int>t3i;
const long double eps=1e-7;
const int inf=0x3f3f3f3f;
const long long INF=1e18;
const double pai=acos(-1.0);
const int mod=1e9+7;
const int N=1e5+10,M=2e6+10;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
//__builtin_popcountll(x)
LL dp[N],a[N];
int p[5];
void solve()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],dp[i]=-INF;
	dp[0]=0;
	queue<PLL>q;
	q.push({0,0});
	while(q.size()){
		auto [ps,nw]=q.front();q.pop();
		if(nw<dp[ps]) continue;
		for(int i=1;i<=4;i++) p[i]=i;
		do{
			LL pos=ps,now=nw;
			bool ok=true;
			for(int i=1;i<=4;i++){
				LL x=pos+p[i];
				if(x<=n&&now+a[x]>=0) dp[x]=max(dp[x],now+a[x]),pos=x,now+=a[x];
				else{
					ok=false;
					break;
				}
			}
			if(ok) q.push({pos,now});
		}while(next_permutation(p+1,p+5));
	}
	if(dp[n]>=0) printf("%lld\n",dp[n]);
	else printf("-1\n");
}
int main()
{
	ios::sync_with_stdio(0); 
    cin.tie(0);
    cout.tie(0);
    int tt;tt=1;
   	//cin>>tt;
    while(tt--){
        solve();
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    static long max=Integer.MIN_VALUE;
    static int[] step=new int[]{1,2,3,4};//走1 2 3 4步的卡牌
    public static void normoaltune(int start,long[] num,long coin,int steps,int[] flag){
        //往后走十步的所有可能情况 取最大值
        if (coin<0)
            return ;
        if (steps==4){
            max=Math.max(max,coin);
            return;
        }
        for (int i = 0; i < 4; i++) {//依次使用卡牌 获取到硬币
            if (flag[i]==0){//没有被使用过
                flag[i]=1;//标记为使用
                normoaltune(start+step[i],num,coin+num[start+step[i]],steps+1,flag);
                flag[i]=0;//回溯为未使用的状态
            }
        }
    }
    public static void lasttune(int start,int finalstep,long[] num,long coin,int[] flag){//最后几步路
        if (coin<0)//小于0 坠机
            return ;
        if (start>finalstep)//越过了 坠机
            return;

        if (start==finalstep){//到达终点 保存最大值
            max=Math.max(max,coin);
        }

        for (int i = 0; i < 4; i++) {
            if (flag[i]==0&&start+step[i]<=finalstep){//卡牌没有被使用过 这段代码类似于走10步的代码
                flag[i]=1;//标记为使用
                lasttune(start+step[i],finalstep,num,coin+num[start+step[i]],flag);
                flag[i]=0;//回溯为未使用的状态
            }
        }
    }

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine();
        long[] nums=new long[n+1];
        for (int i = 0; i < n; i++) {
            nums[i+1]=in.nextLong();
        }
        int nor=n/10;//完整的十步
        int last=n%10;//最后几步

        long coin=0;
        boolean isreach=false;
        for (int i = 0; i < nor; i++) {
            max=Integer.MIN_VALUE;//初始化为最小值
            int[] flag=new int[4];
            normoaltune(i*10,nums,coin,0,flag);//往后走十步
            coin=max;
            if (coin<0) {
                //到不了 寄了
                isreach=true;
                break;
            }
        }
        if (isreach){//到不了
            System.out.println(-1);
        }else{
            //能到
            if (last==0)//正好是10的倍数 那就不用走最后几步了
                System.out.println(coin);
            else {//否则要走最后几步
                max=Integer.MIN_VALUE;//初始化为最小值
                int[] flag=new int[4];
                lasttune(n-last,n,nums,coin,flag);
                coin=max;
                if (coin<0)//硬币为负 到不了终点
                    System.out.println(-1);
                else//为正就输出
                    System.out.println(coin);
            }
        }
    }
}