题解 | 乌龟棋-NOIP2010提高组复赛

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 360,
    M = 41;

int n, m;
int score[N];
int f[M][M][M][M];

int main()
{
    int b[5] = { 0 };
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%d", &score[i]);

    for (int i = 0; i < m; i++)
    {
        int t;
        scanf("%d", &t);
        b[t]++;
    }

    for (int A = 0; A <= b[1]; A++)
        for (int B = 0; B <= b[2]; B++)
            for (int C = 0; C <= b[3]; C++)
                for (int D = 0; D <= b[4]; D++)
                {
                    int t = score[A + B * 2 + C * 3 + D * 4];
                    int &v = f[A][B][C][D];
                    v = t;
                    if (A) v = max(v, f[A - 1][B][C][D] + t);
                    if (B) v = max(v, f[A][B - 1][C][D] + t);
                    if (C) v = max(v, f[A][B][C - 1][D] + t);
                    if (D) v = max(v, f[A][B][C][D - 1] + t);
                }

    printf("%d\n", f[b[1]][b[2]][b[3]][b[4]]);
    return 0;
}