乌龟棋

题目地址:

https://ac.nowcoder.com/acm/problem/16590

基本思路：

比较明显的记忆化搜索，和前两天的一题比较像。
我们使用记忆化搜索令表示位于的位置使用了个一步的卡片,个两步的卡片,个三步的卡片，个四步的卡片,
那么我们只要卡片足够就能通过使用相应卡片往,,, 这些位置转移,
那么如果我们不使用记忆化，这样搜索的复杂度理论上是的指数级别，肯定会,
因此我们使用记录使用了个一步的卡片,个两步的卡片,个三步的卡片，个四步的卡片的结果,
那么由于每种卡片数目不超过,因此此时的复杂度最高为,很明显能够通过。

同时如果我们直接也是可以的,我们有如下转移方程:

int pos = 1 + c1 + 2 * c2 + 3 * c3 + 4 * c4;
if (c1 - 1 >= 0) dp[c1][c2][c3][c4] = max(dp[c1][c2][c3][c4], dp[c1 - 1][c2][c3][c4] + a[pos - 1]);
if (c2 - 1 >= 0) dp[c1][c2][c3][c4] = max(dp[c1][c2][c3][c4], dp[c1][c2 - 1][c3][c4] + a[pos - 2]);
if (c3 - 1 >= 0) dp[c1][c2][c3][c4] = max(dp[c1][c2][c3][c4], dp[c1][c2][c3 - 1][c4] + a[pos - 3]);
if (c4 - 1 >= 0) dp[c1][c2][c3][c4] = max(dp[c1][c2][c3][c4], dp[c1][c2][c3][c4 - 1] + a[pos - 4]);

如果使用，要注意加上最后一个位置。

参考代码：

记忆化搜索：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false); cin.tie(0)
#define ll long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int maxn = 550;
int n,m,x,a[maxn],b[5];
int dp[50][50][50][50]; // 每种卡片数量不超过40;
int dfs(int pos,int c1,int c2,int c3,int c4) {
  if (pos == n) return a[pos]; // 终止条件,卡片用完且到头了;
  if (dp[c1][c2][c3][c4] != 0) return dp[c1][c2][c3][c4]; // 记忆化过程;
  int ans = 0;
  if (c1 + 1 <= b[1]) ans = max(ans, dfs(pos + 1, c1 + 1, c2, c3, c4));
  if (c2 + 1 <= b[2]) ans = max(ans, dfs(pos + 2, c1, c2 + 1, c3, c4));
  if (c3 + 1 <= b[3]) ans = max(ans, dfs(pos + 3, c1, c2, c3 + 1, c4));
  if (c4 + 1 <= b[4]) ans = max(ans, dfs(pos + 4, c1, c2, c3, c4 + 1));
  return dp[c1][c2][c3][c4] = ans + a[pos];
}
signed main() {
  IO;
  cin >> n >> m;
  rep(i, 1, n) cin >> a[i];
  rep(i, 1, m) cin >> x, b[x]++;
  int ans = dfs(1,0,0,0,0);
  cout << ans << '\n';
  return 0;
}

dp:

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false); cin.tie(0)
#define ll long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int maxn = 550;
int n,m,x,a[maxn],b[5];
int dp[50][50][50][50];
signed main() {
  IO;
  cin >> n >> m;
  rep(i, 1, n) cin >> a[i];
  rep(i, 1, m) cin >> x, b[x]++;
  for (int c1 = 0; c1 <= b[1]; c1++) {
    for (int c2 = 0; c2 <= b[2]; c2++) {
      for (int c3 = 0; c3 <= b[3]; c3++) {
        for (int c4 = 0; c4 <= b[4]; c4++) {
          int pos = 1 + c1 + 2 * c2 + 3 * c3 + 4 * c4; // 初始位置从1开始，要加一;
          if (c1 - 1 >= 0) dp[c1][c2][c3][c4] = max(dp[c1][c2][c3][c4], dp[c1 - 1][c2][c3][c4] + a[pos - 1]);
          if (c2 - 1 >= 0) dp[c1][c2][c3][c4] = max(dp[c1][c2][c3][c4], dp[c1][c2 - 1][c3][c4] + a[pos - 2]);
          if (c3 - 1 >= 0) dp[c1][c2][c3][c4] = max(dp[c1][c2][c3][c4], dp[c1][c2][c3 - 1][c4] + a[pos - 3]);
          if (c4 - 1 >= 0) dp[c1][c2][c3][c4] = max(dp[c1][c2][c3][c4], dp[c1][c2][c3][c4 - 1] + a[pos - 4]);
        }
      }
    }
  }
  int ans = dp[b[1]][b[2]][b[3]][b[4]] + a[n];//最后一个位置要加上;
  cout << ans << '\n';
  return 0;
}