做过套娃最多的DP题了,思路不难理解,就是DP过程太长,草草模拟了前面几行,才算是明白了。
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 360, M = 41;
int n, m;
int score[N];
int f[M][M][M][M]; //每种卡牌使用了若干张的走法的最大值
int b[5]; //储存四种牌中每种牌的张数,四种牌分别用下标1,2,3,4储存
//下标0要空出来,所以数组开5个
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ ) scanf("%d", &score[i]);
for (int i = 0; i < m; i ++ )
{
int t;
scanf("%d", &t);
b[t] ++ ; //统计每种卡牌数量
}
for (int A = 0; A <= b[1]; A ++ ) //前四个for循环限制每种卡牌使用次数
for (int B = 0; B <= b[2]; B ++ )
for (int C = 0; C <= b[3]; C ++ )
for (int D = 0; D <= b[4]; D ++ )
{
int t = score[A + B * 2 + C * 3 + D * 4];
int &v = f[A][B][C][D]; //c++语法:之后的v就代表f[A][B][C][D]
v = t; //相当于写:f[A][B][C][D] = t;
if (A) v = max(v, f[A - 1][B][C][D] + t);
if (B) v = max(v, f[A][B - 1][C][D] + t);
if (C) v = max(v, f[A][B][C - 1][D] + t);
if (D) v = max(v, f[A][B][C][D - 1] + t);
}
//题目最后一句:到达终点时刚好用光所有卡牌,所以只要输出所有卡牌都用光的状态即可
printf("%d\n", f[b[1]][b[2]][b[3]][b[4]]);
return 0;
}
模拟草图