题目大意

初始有四种卡片，消耗后分别可以前进 11、22、33 和 44 格。棋盘上每个点都有个分数，求从第 11 格到达第 NN 格途径分数的最大值。

分析

设状态 F[i,j,k,w]F[i, j, k, w] 为使用 ii 张前进 11、……、ww 张前进 44 之后的状态，容易得到转移方程

F[i,j,k,w]=max⁡{dp[i−1,j,k,w]dp[i,j−1,k,w]dp[i,j,k−1,w]dp[i,j,k,w−1]}+a[i+2j+3k+4w] F[i, j, k, w] = \max\left\{ \begin{matrix} dp[i - 1, j, k, w] \\ dp[i, j - 1, k, w] \\ dp[i, j, k - 1, w] \\ dp[i, j, k, w - 1] \end{matrix}\right\} + a[i + 2j + 3k + 4w]

处理一下边界情况，滚动数组即可。

ll dp[50][50][50], aa[400], tt[10];

int main() {
	ll n = rr(), m = rr();
	for (ll i = 1; i <= n; i++) {
		aa[i] = rr();
	}
	for (ll i = 1; i <= m; i++) {
		tt[rr()]++;
	}
	for (ll i = 0; i <= tt[1]; i++) {
		for (ll j = 0; j <= tt[2]; j++) {
			for (ll k = 0; k <= tt[3]; k++) {
				for (ll w = 0; w <= tt[4]; w++) {
					dp[j][k][w] = aa[i * 1 + j * 2 + k * 3 + w * 4 + 1] + max4(
						j == 0 ? 0 : dp[j - 1][k][w],
						k == 0 ? 0 : dp[j][k - 1][w],
						w == 0 ? 0 : dp[j][k][w - 1],
						dp[j][k][w]);
				}
			}
		}
	}

	printf("%lld\n", dp[tt[2]][tt[3]][tt[4]]);
	return 0;
}