小美和大富翁

https://www.nowcoder.com/practice/e6c5d74d6d094e25be7468a21925529b

小美和大富翁

[题目链接](https://www.nowcoder.com/practice/e6c5d74d6d094e25be7468a21925529b)

思路

关键观察

每一轮小美必须使用跳跃 1、2、3、4 的四张卡牌，总共前进 $1+2+3+4=10$ 个城市。因此：

如果 $n$ 不是 10 的倍数，则无法恰好到达第 $n$ 个城市，输出 $-1$ 。
总共需要 $n/10$ 轮，每轮从当前位置前进恰好 10 格。

每轮的选择

在一轮中，小美选择四张卡牌的使用顺序（即 $\{1,2,3,4\}$ 的一个排列），依次跳跃，途中经过 4 个城市。不同的排列会经过不同的中间城市，因此获得的金币总数也不同。

$\{1,2,3,4\}$ 共有 $4!=24$ 种排列，每种排列对应一组经过的城市。例如排列 $(3,1,4,2)$ 表示先跳 3 格、再跳 1 格、再跳 4 格、再跳 2 格，经过的城市偏移量为 $(3,4,8,10)$ 。

贪心策略

由于金币数必须始终 $\geq 0$ ，拥有更多金币意味着更大的灵活性——当前金币越多，未来能选择的排列只会更多，不会更少。因此贪心策略是最优的：每轮在所有可行的排列中，选择金币收益最大的。

具体做法：

枚举 24 种排列，对每种排列模拟 4 步跳跃。
检查每步跳跃后金币是否 $\geq 0$ （可行性检查）。
在所有可行排列中取金币收益最大值。
如果某一轮没有任何可行排列，输出 $-1$ 。

复杂度分析

时间复杂度： $O\!\left(\dfrac{n}{10} \times 24 \times 4\right) = O(n)$
空间复杂度： $O(n)$

代码

C++
Java

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    scanf("%d", &n);
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);

    if(n % 10 != 0){
        printf("-1\n");
        return 0;
    }

    // 预计算 24 种排列对应的累计偏移
    int perms[24][4];
    int cnt = 0;
    int cards[] = {1, 2, 3, 4};
    do {
        int s = 0;
        for(int i = 0; i < 4; i++){
            s += cards[i];
            perms[cnt][i] = s;
        }
        cnt++;
    } while(next_permutation(cards, cards + 4));

    long long coins = 0;
    int rounds = n / 10;

    for(int r = 0; r < rounds; r++){
        int base = r * 10;
        long long best = -1;
        bool found = false;

        for(int p = 0; p < 24; p++){
            long long running = coins;
            bool valid = true;
            long long gain = 0;
            for(int i = 0; i < 4; i++){
                int city = base + perms[p][i];
                running += a[city];
                gain += a[city];
                if(running < 0){
                    valid = false;
                    break;
                }
            }
            if(valid && (!found || gain > best)){
                best = gain;
                found = true;
            }
        }

        if(!found){
            printf("-1\n");
            return 0;
        }
        coins += best;
    }

    printf("%lld\n", coins);
    return 0;
}

import java.util.*;

public class Main {
    static int[][] perms = new int[24][4];
    static int permCnt = 0;

    static void genPerms(int[] arr, int l) {
        if (l == arr.length) {
            int s = 0;
            for (int i = 0; i < 4; i++) {
                s += arr[i];
                perms[permCnt][i] = s;
            }
            permCnt++;
            return;
        }
        for (int i = l; i < arr.length; i++) {
            int tmp = arr[l]; arr[l] = arr[i]; arr[i] = tmp;
            genPerms(arr, l + 1);
            tmp = arr[l]; arr[l] = arr[i]; arr[i] = tmp;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n + 1];
        for (int i = 1; i <= n; i++) a[i] = sc.nextInt();

        if (n % 10 != 0) {
            System.out.println(-1);
            return;
        }

        genPerms(new int[]{1, 2, 3, 4}, 0);

        long coins = 0;
        int rounds = n / 10;

        for (int r = 0; r < rounds; r++) {
            int base = r * 10;
            long best = Long.MIN_VALUE;
            boolean found = false;

            for (int p = 0; p < 24; p++) {
                long running = coins;
                boolean valid = true;
                long gain = 0;
                for (int i = 0; i < 4; i++) {
                    int city = base + perms[p][i];
                    running += a[city];
                    gain += a[city];
                    if (running < 0) {
                        valid = false;
                        break;
                    }
                }
                if (valid) {
                    if (!found || gain > best) {
                        best = gain;
                        found = true;
                    }
                }
            }

            if (!found) {
                System.out.println(-1);
                return;
            }
            coins += best;
        }

        System.out.println(coins);
    }
}