感受

思路









#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 350 + 10;
int dp[maxn][45][45][45];
///dp[pos][x][y][z] 剩余x张1, y张2, z张3
int n, m;
int a[maxn];
int num[5];
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }
    int v;
    for(int i = 1; i <= m; i++){
        scanf("%d", &v); num[v]++;
    }
    memset(dp, -1, sizeof(dp));
    dp[1][num[1]][num[2]][num[3]] = a[1];
    for(int i = 2; i <= n; i++){
        for(int x = num[1]; x >= 0; x--){
            for(int y = num[2]; y >= 0; y--){
                for(int z = num[3]; z >= 0; z--){
                    int q = (i - 1) - (num[1] - x) - 2 * (num[2] - y) - 3 * (num[3] - z);
                    if(q % 4) continue;
                    q /= 4; if(q > num[4]) continue;
                    if(x != num[1] && dp[i - 1][x + 1][y][z] >= 0) dp[i][x][y][z] = max(dp[i][x][y][z], dp[i - 1][x + 1][y][z] + a[i]);
                    if(y != num[2] && i > 2 && dp[i - 2][x][y + 1][z] >= 0) dp[i][x][y][z] = max(dp[i][x][y][z], dp[i - 2][x][y + 1][z] + a[i]);
                    if(z != num[3] && i > 3 && dp[i - 3][x][y][z + 1] >= 0) dp[i][x][y][z] = max(dp[i][x][y][z], dp[i - 3][x][y][z + 1] + a[i]);
                    if(i > 4 && dp[i - 4][x][y][z] >= 0) dp[i][x][y][z] = max(dp[i][x][y][z], dp[i - 4][x][y][z] + a[i]);
                 }
            }
        }
    }
    printf("%d\n", dp[n][0][0][0]);
    return 0;
}