本来应该是f[i][a][b][c][d]的,但是因为这几个变量并不相互独立,存在依赖关系
i=a+2b+3c+4*d,所以可以优化掉一维,有效地降低了时间复杂度并且节省了空间。
f[a][b][c][d]代表分别用了a,b,c,d张分别走1,2,3,4步的牌,走了u=a+2b+3c+4*d步
的方案的最大价值,
f[a][b][c][d]=max(f[a-1][b][c][d],f[a][b-1][c][d],f[a][b][c-1][d],f[a][b][c][d-1])+w[u]
f[cnt[1]][cnt[2]][cnt[3]][cnt[4]]即为所求
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#define endl '\n'
#define int long long
using namespace std;
const int N = 45;
const int M = 360;
int f[N][N][N][N];
int w[M];
int cnt[5];
int n, m;
signed main(void)
{
std::ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 0; i < n; i++)
{
cin >> w[i];
}
for (int i = 0; i < m; i++)
{
int x;
cin >> x;
cnt[x]++;
}
// memset(f[0], -0x3f, sizeof(f[0]));
// f[0][0][0][0] = 0;
for (int a = 0; a <= cnt[1]; a++)
{
for (int b = 0; b <= cnt[2]; b++)
{
for (int c = 0; c <= cnt[3]; c++)
{
for (int d = 0; d <= cnt[4]; d++)
{
int u = a + 2 * b + 3 * c + 4 * d;
f[a][b][c][d] = w[u];
int &t = f[a][b][c][d];
if (a)
t = max(t, f[a - 1][b][c][d] + w[u]);
if (b)
t = max(t, f[a][b - 1][c][d] + w[u]);
if (c)
t = max(t, f[a][b][c - 1][d] + w[u]);
if (d)
t = max(t, f[a][b][c][d - 1] + w[u]);
}
}
}
}
cout << f[cnt[1]][cnt[2]][cnt[3]][cnt[4]] << endl;
return 0;
}