题解 | #乌龟棋#

这道题可以用多维dp(4维，每一维代表一种卡片)或者记忆化搜索解决，这里奉上dp的解法，其中的状态转移方程可以推出为：

//i,j,k,l分别代表步长为1,2,3,4
int value = 1;//因为乌龟初始位置为1的格子
value += i*1 + j*2 + k*3 + l*4;
//value代表当前走到的位置
if(i > 0)
dp[i][j][k][l] = max(dp[i - 1][j][k][l] + a[value], dp[i][j][k][l]);
if(j > 0)
dp[i][j][k][l] = max(dp[i][j - 1][k][l] + a[value], dp[i][j][k][l]);
if(k > 0)
dp[i][j][k][l] = max(dp[i][j][k - 1][l] + a[value], dp[i][j][k][l]);
if(l > 0)
dp[i][j][k][l] = max(dp[i][j][k][l - 1] + a[value], dp[i][j][k][l]);

代码如下：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define IOS ios::sync_with_stdio(false);
typedef pair<int, int> PII;
typedef long long ll;

const int N = 500;
int dp[50][50][50][50];
int a[N];
int n, m;
int num[5];

int main()
{
    IOS;
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++)
    {
        int k;
        cin >> k;
        switch (k)
        {
        case 1:
            num[1]++;
            break;
        case 2:
            num[2]++;
            break;
        case 3:
            num[3]++;
            break;
        case 4:
            num[4]++;
            break;
        default:
            break;
        }
    }
    dp[0][0][0][0] = a[1];
    for (int i = 0; i <= num[1]; i++)
    {
        for (int j = 0; j <= num[2]; j++)
        {
            for (int k = 0; k <= num[3]; k++)
            {
                for (int l = 0; l <= num[4]; l++)
                {
                    int value = 1;
                    value += i + j * 2 + k * 3 + l * 4;
                    if (i > 0)
                    {
                        dp[i][j][k][l] = max(dp[i - 1][j][k][l] + a[value], dp[i][j][k][l]);
                    }
                    if (j > 0)
                    {
                        dp[i][j][k][l] = max(dp[i][j - 1][k][l] + a[value], dp[i][j][k][l]);
                    }
                    if (k > 0)
                    {
                        dp[i][j][k][l] = max(dp[i][j][k - 1][l] + a[value], dp[i][j][k][l]);
                    }
                    if (l > 0)
                    {
                        dp[i][j][k][l] = max(dp[i][j][k][l - 1] + a[value], dp[i][j][k][l]);
                    }
                }
            }
        }
    }
    cout << dp[num[1]][num[2]][num[3]][num[4]] << endl;
    system("pause");
    return 0;
}