比赛 防止颓废的小练习v0.2 评测结果 AAAAAAAAAA
题目名称 乌龟棋 最终得分 100
用户昵称 KZNS 运行时间 0.219 s
代码语言 C++ 内存使用 100.06 MiB
提交时间 2016-10-18 10:04:29
显示代码纯文本
//KZNS
#include <cstdio>
#include <algorithm>
using namespace std;
#define Nmax 353
int A[Nmax];
int N, M;
int cd[6] = {0};
int F[Nmax][42][42][42] = {0};
void rin() {
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++)
        scanf("%d", A+i);
    int u;
    for (int i = 0; i < M; i++) {
        scanf("%d", &u);
        cd[u]++;
    }
}
void work() {
    int uN = N-1;
    F[0][0][0][0] = A[0];
    int i1;
    int u;
    for (int i = 0; i < uN; i++) {
        for (int i4 = 0; i4 <= cd[4] && i4*4 <= i; i4++) {
            for (int i3 = 0; i3 <= cd[3] && i4*4 + i3*3 <= i; i3++) {
                for (int i2 = 0; i2 <= cd[2] && i4*4 + i3*3 + i2*2 <= i; i2++) {
                    i1 = i - (i4*4 + i3*3 + i2*2);
                    if (i1 > cd[1] || !F[i][i4][i3][i2])
                        continue;
                    u = F[i][i4][i3][i2];
                    if (i4 < cd[4])
                        F[i+4][i4+1][i3][i2] = 
                            max(F[i+4][i4+1][i3][i2], u + A[i+4]);
                    if (i3 < cd[3])
                        F[i+3][i4][i3+1][i2] =
                            max(F[i+3][i4][i3+1][i2], u + A[i+3]);
                    if (i2 < cd[2])
                        F[i+2][i4][i3][i2+1] = 
                            max(F[i+2][i4][i3][i2+1], u + A[i+2]);
                    if (i1 < cd[1])
                        F[i+1][i4][i3][i2] = 
                            max(F[i+1][i4][i3][i2], u + A[i+1]);
                }
            }
        }
    }
    printf("%d\n", F[uN][cd[4]][cd[3]][cd[2]]);
}
int main() {
    freopen("tortoise.in", "r", stdin);
    freopen("tortoise.out", "w", stdout);
    rin();
    work();
    return 0;
}
//UBWH