题解：P1541 [NOIP2010 提高组] 乌龟棋

思路

感觉这道题并没有绿题的难度。

首先看到数据范围，可以发现这里的数据范围都非常小，且每一种卡牌的数量均不会超过 $40$，那么这道题就非常简单了。

考虑使用动态规划算法。

1. 状态定义
   我们定义 $f_{i, j, k, l}$ 为使用了 $i$ 张 $1$ 号牌，$j$ 张 $2$ 号牌，$k$ 张 $3$ 号牌，$l$ 张 $4$ 号牌所能获得的最大价值。
2. 状态转移
   我们采用四重循环来解决状态转移的问题，四重循环分别枚举使用了这四种牌的数量，$i$，$j$，$k$，$l$ 分别表示使用了 $i$ 张 $1$ 号牌，$j$ 张 $2$ 号牌，以此类推。

则每一种转移的代码如下：

int dsj = 1 + i + j * 2 + k * 3 + l * 4; // 走到了哪里
if (i) {
  f[i][j][k][l] = max(f[i][j][k][l], f[i - 1][j][k][l] + a[dsj]); // 1号牌
}
if (j) {
  f[i][j][k][l] = max(f[i][j][k][l], f[i][j - 1][k][l] + a[dsj]); // 2号牌
}
if (k) {
  f[i][j][k][l] = max(f[i][j][k][l], f[i][j][k - 1][l] + a[dsj]); // 3号牌
}
if (l) {
  f[i][j][k][l] = max(f[i][j][k][l], f[i][j][k][l - 1] + a[dsj]); // 4号牌
}

3. 答案
   最后的答案就非常明显了，就是 $f_{k1, k2, k3, k4}$，$k_{i}$ 表示每一种牌的数量。

代码：

#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 355 + 4, kMaxM = 40;

int n, m, b[kMaxN], a[kMaxN], f[kMaxM][kMaxM][kMaxM][kMaxM];

map<int, int> K;

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= m; i++) {
    cin >> b[i], K[b[i]]++;
  }
  f[0][0][0][0] = a[1];
  for (int i = 0; i <= K[1]; i++) {
    for (int j = 0; j <= K[2]; j++) {
      for (int k = 0; k <= K[3]; k++) {
        for (int l = 0; l <= K[4]; l++) {
          int dsj = 1 + i + j * 2 + k * 3 + l * 4;
          if (i) {
            f[i][j][k][l] = max(f[i][j][k][l], f[i - 1][j][k][l] + a[dsj]);
          }
          if (j) {
            f[i][j][k][l] = max(f[i][j][k][l], f[i][j - 1][k][l] + a[dsj]);
          }
          if (k) {
            f[i][j][k][l] = max(f[i][j][k][l], f[i][j][k - 1][l] + a[dsj]);
          }
          if (l) {
            f[i][j][k][l] = max(f[i][j][k][l], f[i][j][k][l - 1] + a[dsj]);
          }
        }
      }
    }
  }
  cout << f[K[1]][K[2]][K[3]][K[4]] << '\n';
  return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=355, M=42;
int a[N], c[7], f[M][M][M][M];
int main()
{
    memset(c, 0, sizeof(c));
    int n, m, x; scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]); 
    for(int i=1; i<=m; i++) scanf("%d", &x), c[x]++;
    memset(f, 0, sizeof(f)); f[0][0][0][0]=a[1];
    for(int i=0; i<=c[1]; i++)
        for(int j=0; j<=c[2]; j++)
            for(int k=0; k<=c[3]; k++)
                for(int l=0; l<=c[4]; l++) 
                {
                    int now=1*i+2*j+3*k+4*l+1;
                    if(i>=1) f[i][j][k][l]=max(f[i][j][k][l], f[i-1][j][k][l]+a[now]);
                    if(j>=1) f[i][j][k][l]=max(f[i][j][k][l], f[i][j-1][k][l]+a[now]);
                    if(k>=1) f[i][j][k][l]=max(f[i][j][k][l], f[i][j][k-1][l]+a[now]);
                    if(l>=1) f[i][j][k][l]=max(f[i][j][k][l], f[i][j][k][l-1]+a[now]);
                }
    printf("%d\n", f[c[1]][c[2]][c[3]][c[4]]);
    return 0;
}