P1541 乌龟棋

发表于 | 分类于 |
字数统计: 624 | 阅读时长 ≈ 2

题面：https://www.luogu.org/problemnew/show/P1541

题意

给定一个棋盘，上面由N个格子。每个格子上面有一个对应的分数。同时有若干张卡片上面分别是1，2，3，4。每张卡片使用后可以前进对应的格数。显然不同的使用卡片会导致不同的分数。求最后能获得的最大分数。

解法

乍看之下，是个dp
但是好像不是很好写，想了一段时间也没想出来状态。
然后发现由于卡片只有四种。
我们可以用$dp[c1][c2][c3][c4][i]$表示每种卡片分别用了$c1, c2, c3, c4$张时到达第$i$个格子时获得的最大分数。
这样每次转移就是多一张卡片带来的结果改变。
但这样发现空间需要$40 ^4 \cdot 120$空间开不下。
发现每次转移的时候前一个状态只会在前四个格子内向后转移。所以可以用取模只需要5个位置
但是这样时间复杂度到达$O(40 ^4 \cdot 120)$会超时
然后发现蠢了，可以去掉最后一个维度，因为用了多少张卡片会有到达一个固定的位置。
所以就去掉最后一个维度，直接dp就好了
回过头来想，这个就是一个多重背包问题。
每个物品的体积为1，价值为格子对应的分数。
做完了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 1000 + 10;
int a[maxn], b[maxn];
int dp[40][40][40][40];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 0; i < m; i++)
    {
        int t;
        cin >> t;
        b[t]++;
    }
    memset(dp, -0x7f, sizeof(dp));
    dp[0][0][0][0] = a[1];
        for(int c1 = 0; c1 <= b[1]; c1++)
            for(int c2 = 0; c2 <= b[2]; c2++)
                for(int c3 = 0; c3 <= b[3]; c3++)
                    for(int c4 = 0; c4 <= b[4]; c4++)
                    {
                        int temp = c1 + c2 * 2 + c3 * 3 + c4 * 4 + 1;
                        if(c4 >= 1)
                            dp[c1][c2][c3][c4] = max(dp[c1][c2][c3][c4], dp[c1][c2][c3][c4 - 1] + a[temp]);
                        if(c3 >= 1)
                            dp[c1][c2][c3][c4] = max(dp[c1][c2][c3][c4], dp[c1][c2][c3 - 1][c4] + a[temp]);
                        if(c2 >= 1)
                            dp[c1][c2][c3][c4] = max(dp[c1][c2][c3][c4], dp[c1][c2 - 1][c3][c4] + a[temp]);
                        if(c1 >= 1)
                            dp[c1][c2][c3][c4] = max(dp[c1][c2][c3][c4], dp[c1 - 1][c2][c3][c4] + a[temp]);
                    }
    cout << dp[b[1]][b[2]][b[3]][b[4]] << endl;
    return 0;
}