题目背景

小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。

题意描述

乌龟棋的棋盘是一行 $N$ 个格子，每个格子上有一个分数。

棋盘第 $1$ 格是唯一的起点，第 $N$ 格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。

乌龟棋中 $M$ 张爬行卡片，分成 $4$ 种不同的类型（ $M$ 张卡片中不一定包含所有 $4$ 种类型的卡片）。

每种类型的卡片上分别标有 $1,2,3,4$ 四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。

游戏中，玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。

游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到该格子相应的分数。

玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。

很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同。

小明想要找到一种卡片使用顺序使得最终游戏得分最多。

现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到多少分吗？

输入格式

每行中两个数之间用一个空格隔开。

第 $1$ 行包括 $2$ 个正整数 $N,M$ ，分别表示棋盘格子数和爬行卡片数。

第 $2$ 行包括 $N$ 个非负整数， $a_1,a_2,…,a_N$ 表示棋盘第 $i$ 个格子上的分数。

第 $3$ 行 $M$ 个整数， $b_1,b_2,…,b_M$ ，表示 $M$ 张爬行卡片上的数字。

输入数据保证到达终点时刚好用光 $M$ 张爬行卡片。

输出格式

输出仅有一行，包括 $1$ 个整数 $ans$ ，表示小明最多能得到的分数。

Input & Output 's examples

Input 's eg

9 5
6 10 14 2 8 8 18 5 17
1 3 1 2 1

Output 's eg

样例解释

小明使用爬行卡片顺序为 $1,1,3,1,2$ ,得到的分数为 $6+10+14+8+18+17=73$ 。

注意，由于起点是 $1$ ，所以自动获得第 $1$ 格的分数 $6$

数据范围和约定

对于 $30\%$ 数据,有 $1≤N≤30,1≤M≤12$ 。

对于 $50\%$ 的数据,有 $1≤N≤120,1≤M≤50$ ，且有全部 $4$ 种爬行卡片，每种卡片的张数不会超过 $20$ 。

对于 $100\%$ 的数据,有 $1≤N≤350,1≤M≤120$ ，且有全部 $4$ 种爬行卡片，每种卡片的张数不会超过 $40$ ；

对于其他上面未提到的变量，保证 $0≤a_i≤100,1≤i≤N,1≤b_i≤4,1≤i≤M$ 。

分析

~~真的是NOIP里最简单的DP题了……~~

不难发现，卡片的种类数与每一种卡片的数量都极少。因此，我们可以直接开一个四维数组表示状态。

设 $f_{i,j,k,l}$ 表示四种卡片分别使用了 $i , j , k , l$ 张所能得到的最大得分，每一次转移时暴力枚举最后一次使用的卡片即可。

时间复杂度 $O(g_1 \times g_2 \times g_3 \times g_4)$ ，其中 $g_i$ 表示第 $i$ 种卡牌的数量，最大为 $40$ 。足以通过本题。

当然，你也可以选择使用滚动数组压掉一维。这样就可以处理 $g_i < 90$ 的情况。

剩下的见代码注释。

Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long
#define I inline
#define N 45

using namespace std;

int n , m;
int g[5];

ll a[10001];
ll ans = 0;
ll f[N][N][N][N];

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

【NOIP2010】乌龟棋-题解