乌龟棋_牛客博客

题意： 共 $n$ 个格子，每个格子有相应的分数， $m$ 张卡牌，卡牌上的数字 $x$ 表示可以从当前格子往后走 $x$ 格，初始在一号格，自动得到一号格的分数，问选择卡牌进行走格子的方式中可获得的最大值为多少。
数据范围： $n\leq350$ ，卡牌数字 $x\in[1,4]$ ，每种卡牌数量为 $[0,min(40,m)]$ ，保证 $\sum_{i=1}^nb_i=n-1$
题解：
这种数据范围自然想到的是爆搜加剪枝。
由于最多有 $40^4$ 个状态，因为先使用一次 $1$ 号牌再使用一次 $2$ 号牌，与先使用一次 $2$ 号牌，再使用一次 $1$ 号牌是一种情况，如果重复递归的话复杂度爆炸，故想到记忆化搜索。 $dfs(u,a,b,c,d)$ 表示剩余 $cnt_a-a$ 个 $1$ 号牌， $cnt_b-b$ 个 $2$ 号牌， $cnt_c-c$ 个 $3$ 号牌， $cnt_d-d$ 个 $4$ 号牌，当前在 $u$ 号格子走到 $n$ 号格子可得到的最大分数。每次记忆化一下 $f[a][b][c][d]$ 即可。
代码：

#include<bits/stdc++.h>
using namespace std;

const int N = 50;
const int M = 360;
int f[N][N][N][N];
int n, m;
int cnt[5];
int v[N];
int score[M];

int dfs(int u, int a, int b, int c, int d) {
    if(u == n) return score[u];
    if(~f[a][b][c][d]) return f[a][b][c][d];

    int res = 0;
    if(cnt[1] > a) res = max(res, dfs(u + 1, a + 1, b, c, d));
    if(cnt[2] > b) res = max(res, dfs(u + 2, a, b + 1, c, d));
    if(cnt[3] > c) res = max(res, dfs(u + 3, a, b, c + 1, d));
    if(cnt[4] > d) res = max(res, dfs(u + 4, a, b, c, d + 1));
    return f[a][b][c][d] = score[u] + res;
} 

int main()
{
    memset(f, -1, sizeof f);
    memset(cnt, 0, sizeof cnt);
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d", &score[i]);
    for(int i = 1, x; i <= m; i++) {
        scanf("%d", &x); 
        cnt[x]++;
    }

    printf("%d\n", dfs(1, 0, 0, 0, 0));

    return 0;
}