NOIP2010乌龟棋

发布于 2019-10-28  503 次阅读

题面

(luogu传送门)[https://www.luogu.org/problem/P1541]

题目背景

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

题目描述

乌龟棋的棋盘是一行$N$N个格子，每个格子上一个分数（非负整数）。棋盘第1格是唯一的起点，第$N$N格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。
乌龟棋中M$M$张爬行卡片，分成4种不同的类型（MM张卡片中不一定包含所有4$4$种类型的卡片，见样例），每种类型的卡片上分别标有$1,2,3,4$1,2,3,4四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。
游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。
很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小明想要找到一种卡片使用顺序使得最终游戏得分最多。
现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到多少分吗？

输入格式

每行中两个数之间用一个空格隔开。
第$1$行2$2$个正整数$N,M$，分别表示棋盘格子数和爬行卡片数。
第$2$行$N$个非负整数，$a_1,a_2,…,a_N$其中$a_i$表示棋盘第$i$个格子上的分数。
第$3$行$M$个整数，$b_1,b_2,…,b_M$，表示M张爬行卡片上的数字。
输入数据保证到达终点时刚好用光$M$张爬行卡片。

输出格式

$1$个整数，表示小明最多能得到的分数。

题解

假做法（记忆化搜索）

我们可以设一个$f[i]$表示$i~n$的最大得分，我们还要维护一个$vis[]$，一旦这个卡片被搜索过，我们就不用这个卡片，转而用其他没有被用过的卡片更新状态。

真做法（记忆化搜索）

发现标记$vis$数组效率太低，我们可以多设三维状态优化这个问题。

我们设$f[a][b][c][d]$为使用了$a$次一号卡片，$b$次二号卡片，$c$次三号卡片，$d$次四号卡片，那么我们乌龟移动的位置可以表示为：

$$1 + a \times 1 + b \times 2 + c \times 3 + d \times 4$$

我们从1开始走，所以要加上一个1

一个显然成立的方程式：

代码

#include <cstdio>

#define pos a + b * 2 + c * 3 + d * 4 + 1
#define maxn 350
#define max(a, b) a > b ? a : b
#define fors(a, b, c, d) for (register int a = b; a <= c; a += d)

int n, m, map[maxn], ca[5], f[44][44][44][44];

int dfs(const int a, const int b, const int c, const int d) //const为防止写代码时犯zz错误
{
    if (f[a][b][c][d])
        return f[a][b][c][d];

    if (a == ca[1] and b == ca[2] and c == ca[3] and d == ca[4])
        return map[n];

    if (a < ca[1])
        f[a][b][c][d] = max(f[a][b][c][d], map[pos] + dfs(a + 1, b, c, d));
    if (b < ca[2])
        f[a][b][c][d] = max(f[a][b][c][d], map[pos] + dfs(a, b + 1, c, d));
    if (c < ca[3])
        f[a][b][c][d] = max(f[a][b][c][d], map[pos] + dfs(a, b, c + 1, d));
    if (d < ca[4])
        f[a][b][c][d] = max(f[a][b][c][d], map[pos] + dfs(a, b, c, d + 1));

    return f[a][b][c][d];
}

int main()
{

    scanf("%d%d", &n, &m);

    fors(i, 1, n, 1)
    scanf("%d", &map[i]);

    fors(i, 1, m, 1)
    {
        int x;
        scanf("%d", &x);
        ca[x]++;
    }

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

    return 0;
}

THE END