题目描述
小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。
乌龟棋的棋盘是一行 N 个格子，每个格子上一个分数（非负整数）。棋盘第 1格是唯一的起点，第 N 格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。
乌龟棋中 M 张爬行卡片，分成 4 种不同的类型（M 张卡片中不一定包含所有 4 种类型的卡片，见样例），每种类型的卡片上分别标有 1,2,3,4 四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。
游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。
很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小明想要找到一种卡片使用顺序使得最终游戏得分最多。
现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到多少分吗
定义状态f[i][j][k][l]为各种卡片还剩i,j,k,l张时的分数。
转移就是简单的从前往后转移，保留最大。
但是第一次写的时候有个问题，状态没有想清楚，当时把状态只定义了两维，dp[i][5]，表示第i格的状态，0,1,2,3,4分别表示得分和卡牌的数量，转移就从前面的格子-1,-2,-3,-4转移过来，（然后样例一直都没过qwq）。其实问题在于，当前位置这个状态很鸡肋，如果我知道当前四张卡牌的花费状态，就一定能知道当前的位置。如果只记录位置，那么几乎必然会丢失信息，因为一个格子可能对应多种不同的卡牌状态，直接这样转移只能保存一种状态，而且保存的是局部最优解。（比如，前面-1,-2,-3,-4有两种情况的得分都相同，那我只能保留某一个情况，极有可能把更优情况舍弃了，或者得分目前更少的卡牌状态更有潜力）
如果用卡牌数目来表示状态，那自然是非常清楚明了的。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//#define int ll
#define DBG
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define rrep(i, b, a) for (int i = (b); i >= (a); i--)
#ifdef DBG
#define dbg(...) (cout << ":D ", _((char*)#__VA_ARGS__, __VA_ARGS__))
template <typename t>
void _(char* p, t x) {
cout << p << '=' << x << '\n';
}
template <typename t, typename... a>
void _(char* p, t x, a... y) {
while (*p != ',') cout << *p++;
cout << '=' << x << ',';
_(p + 1, y...);
}
#else
#define dbg(...) ((void)0)
#endif
const int N = 44;
int f[N][N][N][N];
int s[5];
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin >> n >> m;
int a[n+1];
rep(i,1,n) cin >> a[i];
rep(i,1,m) {
int x;
cin >> x;
s[x]++;
}
f[0][0][0][0] = a[1];
rep(i,0,s[1]) {
rep(j,0,s[2]) {
rep(k,0,s[3]) {
rep(l,0,s[4]) {
if (i == 0 && j == 0 && k == 0 && l == 0) continue;
int mx = 0;
int cur = 1 + i * 1 + j * 2 + k * 3 + l * 4;
if(i) mx = max(mx,f[i-1][j][k][l]+a[cur]);
if (j) mx = max(mx, f[i][j-1][k][l] + a[cur]);
if (k) mx = max(mx, f[i][j][k-1][l] + a[cur]);
if (l) mx = max(mx, f[i][j][k][l-1] + a[cur]);
f[i][j][k][l] = mx;
}
}
}
}
cout << f[s[1]][s[2]][s[3]][s[4]] << endl;
return 0;
} /* created: 2024-11-30 17:56 author: Egrvigrf */