【ACWing】312. 乌龟棋

https://www.acwing.com/problem/content/314/

小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。乌龟棋的棋盘只有一行，该行有 N N N个格子，每个格子上一个分数（非负整数）。棋盘第 1 1 1格是唯一的起点，第 N N N格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。乌龟棋中共有 M M M张爬行卡片，分成 4 4 4种不同的类型（ M M M张卡片中不一定包含所有 4 4 4种类型的卡片），每种类型的卡片上分别标有 1 1 1、 2 2 2、 3 3 3、 4 4 4四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小明想要找到一种卡片使用顺序使得最终游戏得分最多。现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到多少分吗？

输入格式：
输入文件的每行中两个数之间用一个空格隔开。
第 1 1 1行 2 2 2个正整数 N N N和 M M M，分别表示棋盘格子数和爬行卡片数。
第 2 2 2行 N N N个非负整数， a 1 , a 2 , … … , a N a_1,a_2,……,a_N a1​,a2​,……,aN​，其中 a i a_i ai​表示棋盘第 i i i个格子上的分数。
第 3 3 3行 M M M个整数， b 1 , b 2 , … … , b M b_1,b_2,……,b_M b1​,b2​,……,bM​，表示 M M M张爬行卡片上的数字。输入数据保证到达终点时刚好用光 M M M张爬行卡片。

输出格式：
输出只有 1 1 1行，包含 1 1 1个整数，表示小明最多能得到的分数。

数据范围：
1 ≤ N ≤ 350 1≤N≤350 1≤N≤350
1 ≤ M ≤ 120 1≤M≤120 1≤M≤120
0 ≤ a i ≤ 100 0≤a_i≤100 0≤ai​≤100
1 ≤ b i ≤ 4 1≤b_i≤4 1≤bi​≤4
每种爬行卡片的张数不会超过 40 40 40。

设 f [ x 1 ] [ x 2 ] [ x 3 ] [ x 4 ] f[x_1][x_2][x_3][x_4] f[x1​][x2​][x3​][x4​]是已经用了 x k x_k xk​张 k k k步卡片后得到的最大分数，那么可以按照最后一张卡片用的是哪种来分类，例如如果最后用的是 2 2 2步卡片，则最大分数为 f [ x 1 ] [ x 2 − 1 ] [ x 3 ] [ x 4 ] + a [ 1 + x 1 + 2 x 2 + 3 x 3 + 4 x 4 ] f[x_1][x_2-1][x_3][x_4]+a[1+x_1+2x_2+3x_3+4x_4] f[x1​][x2​−1][x3​][x4​]+a[1+x1​+2x2​+3x3​+4x4​]。代码如下：

#include 
using namespace std;

const int N = 360, M = 45;
int n, m;
int a[N], b[5];
int f[M][M][M][M];

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i <= m; i++) {
    int x;
    scanf("%d", &x);
    b[x]++;
  }

  f[0][0][0][0] = a[1];
  for (int x1 = 0; x1 <= b[1]; x1++)
    for (int x2 = 0; x2 <= b[2]; x2++)
      for (int x3 = 0; x3 <= b[3]; x3++)
        for (int x4 = 0; x4 <= b[4]; x4++) {
          int &v = f[x1][x2][x3][x4];
          int s = a[1 + x1 + 2 * x2 + 3 * x3 + 4 * x4];
          if (x1) v = max(v, f[x1 - 1][x2][x3][x4] + s);
          if (x2) v = max(v, f[x1][x2 - 1][x3][x4] + s);
          if (x3) v = max(v, f[x1][x2][x3 - 1][x4] + s);
          if (x4) v = max(v, f[x1][x2][x3][x4 - 1] + s);
        }

  printf("%dn", f[b[1]][b[2]][b[3]][b[4]]);
}

时空复杂度 O ( M 1 M 2 M 3 M 4 ) O(M_1M_2M_3M_4) O(M1​M2​M3​M4​)， M i M_i Mi​是 i i i步卡片的个数。