更新美团810笔试第四题

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int solve(int n, const vector<int>&amp; a) {
    int dp[16][n + 1];
    memset(dp, -1, sizeof(dp)); // 初始化 dp 数组，初始值为 -1

    dp[15][0] = 0;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 16; ++j) {
            if (dp[j][i] < 0) {
                continue;
            }
            for (int k = 0; k < 4; ++k) {
                if ((j &amp; (1 << k)) == 0) {
                    continue;
                }
                int ni = i + k + 1;
                int nj = j ^ (1 << k);
                if (ni > n) {
                    continue;
                }
                if (nj == 0) {
                    nj = 15;
                }
                dp[nj][ni] = max(dp[nj][ni], dp[j][i] + a[ni]);
            }
        }
    }

    int res = -1;
    for (int i = 1; i < 16; ++i) {
        res = max(res, dp[i][n]);
    }

    return res;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    cout << solve(n, a) << endl; // 输出最大收益

    return 0;
}