思路分析
首先想到的做法应该是dfs,用全排列来写,那假设四种卡片每种都有30张(总卡片数最多120)
复杂度就是$C(120,30)$ * $C(90,30)$ * $C(60,30)$ * $C(30,30)$将近1^69,指数级别,超时
所以就要用DP来考虑了
状态表示我们发现n要一维,A,B,C,D分别各要一维,复杂度就是350 * 40 * 40 * 40 * 40将近一个亿,
然后D可以通过n,A,B,C算出来,减少一维,但空间会爆,所以我们决定把n这一维换掉,即最终状态表示为f(A, B, C, D)
n = 1 + A + 2 * B + 3 * C + 4 * D, n表示现在走到哪个位置
接下来用dp分析即可
状态表示
状态计算
代码实现
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510, M = 45;
int n, m;
int w[N], s[M]; // s数组来记录1,2,3,4四种卡片出现的次数
int f[M][M][M][M];
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++) cin >> w[i];
while (m -- )
{
int x;
cin >> x;
s[x] ++; // 记录四种卡片出现的次数
}
f[0][0][0][0] = w[1]; // 初始位置是在第一个格子
for(int A = 0; A <= s[1]; A ++)
for(int B = 0; B <= s[2]; B ++)
for(int C = 0; C <= s[3]; C ++)
for(int D = 0; D <= s[4]; D ++)
{
int score = w[1 + A + 2 * B + 3 * C + 4 * D]; // 记录当前走到位置的分数
int& v = f[A][B][C][D]; // 引用别名,原名太长了
if(A) v = max(v, f[A - 1][B][C][D] + score);
if(B) v = max(v, f[A][B - 1][C][D] + score);
if(C) v = max(v, f[A][B][C - 1][D] + score);
if(D) v = max(v, f[A][B][C][D - 1] + score);
}
cout << f[s[1]][s[2]][s[3]][s[4]] << endl;
return 0;
}