比赛 |
防止颓废的小练习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