乌龟棋(DP)_牛客博客

乌龟棋

思路

最优值问题，显然可以通过 $dp$ 解决，我们定义 $dp[i][j][k][l]$ 表示到达 $1 + i * 2 * j + 3 * k + 4 * l$ 这个点之前已经走过的价值最大的值( $i, j, k, l$ 分别是走一步，走两步，走三步，走四步的数量)，显然这个点我们可以从 $dp[i - 1][j][k][l]$ 或或者 $dp[i][j - 1][k][l]$ 或者 $dp[i][j][k - 1][l]$ 或者 $dp[i][j][k][l - 1]$ 转移过来，因此我们只需要用四重 $for$ 循环来进行 $dp$ 即可得到我们的最优值，同时输出答案加上点 $n$ 的权值即可。

代码

/*
  Author : lifehappy
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define endl '\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

const double pi = acos(-1.0);
const double eps = 1e-7;
const int inf = 0x3f3f3f3f;

inline ll read() {
    ll f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return f * x;
}

void print(ll x) {
    if(x < 10) {
        putchar(x + 48);
        return ;
    }
    print(x / 10);
    putchar(x % 10 + 48);
}

const int N = 400;

int n, m, num[5], cost[N], dp[45][45][45][45];

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    n = read(), m = read();
    for(int i = 1; i <= n; i++) {
        cost[i] = read();
    }
    for(int i = 1; i <= m; i++) {
        num[read()]++;
    }
    for(int i = 0; i <= num[1]; i++) {
        for(int j = 0; j <= num[2]; j++) {
            for(int k = 0; k <= num[3]; k++) {
                for(int l = 0; l <= num[4]; l++) {
                    int pos = 1 + i + 2 * j + 3 * k + 4 * l;
                    if(i)   dp[i][j][k][l] = max(dp[i][j][k][l], dp[i - 1][j][k][l] + cost[pos - 1]);
                    if(j)   dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j - 1][k][l] + cost[pos - 2]);
                    if(k)   dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k - 1][l] + cost[pos - 3]);
                    if(l)   dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k][l - 1] + cost[pos - 4]);
                }
            }
        }
    }
    //我们记录的是dp[num[1]][num[2]][num[3]][num[4]]之前的花费，所以答案还要加上这个点的花费。
    printf("%d\n", dp[num[1]][num[2]][num[3]][num[4]] + cost[n]);
    return 0;
}