AcWing 312. 乌龟棋
原题链接
简单
#include<iostream>
#include<cstring>
using namespace std;
const int N = 41, M = 360;
int a[M], m[5];
int f[N][N][N][N];
int n, m1;
int main()
{
scanf("%d%d", &n, &m1);
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
for(int i = 1; i <= m1; i++)
{
int t;
scanf("%d", &t);
m[t]++;
}
for(int i = 0; i <= m[1]; i++)
for(int j = 0; j <= m[2]; j++)
for(int k = 0; k <= m[3]; k++)
for(int t = 0; t <= m[4]; t++)
{
int v = a[i * 1 + j * 2 + k * 3 + t * 4];
f[i][j][k][t] = v;
if(i) f[i][j][k][t] = max(f[i][j][k][t], f[i - 1][j][k][t] + v);
if(j) f[i][j][k][t] = max(f[i][j][k][t], f[i][j - 1][k][t] + v);
if(k) f[i][j][k][t] = max(f[i][j][k][t], f[i][j][k - 1][t] + v);
if(t) f[i][j][k][t] = max(f[i][j][k][t], f[i][j][k][t - 1] + v);
}
printf("%d", f[m[1]][m[2]][m[3]][m[4]]);
return 0;
}