AcWing 312. 乌龟棋    原题链接    简单

作者： 作者的头像   yxc ,  2019-08-18 22:51:01 ,  所有人可见 ,  阅读 6526

55


17

算法

(线性DP) $O(40^4)$

状态表示：$f[b_1, b_2, b_3, b_4]$ 表示所有第 $i$ 种卡片使用了 $b_i$ 张的走法的最大分值。

状态计算：将 $f[b_1, b_2, b_3, b_4]$ 表示的所有走法按最后一步选择哪张卡片分成四类：第 $i$ 类为最后一步选择第 $i$ 种卡片。比如 $i = 2$，则这一类的最大分值是 $f[b_1, b_2 - 1, b_3, b_4] + score[b_1 + 2b_2 + 3b_3 + 4b_4]$。

时间复杂度

一共有 $40^4$ 个状态，每个状态需要 $O(1)$ 的计算量，因此总时间复杂度是 $O(40^4)$。

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 360, M = 41;

int n, m;
int score[N];
int f[M][M][M][M];

int main()
{
    int b[5] = {0};
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%d", &score[i]);

    for (int i = 0; i < m; i ++ )
    {
        int t;
        scanf("%d", &t);
        b[t] ++ ;
    }

    for (int A = 0; A <= b[1]; A ++ )
        for (int B = 0; B <= b[2]; B ++ )
            for (int C = 0; C <= b[3]; C ++ )
                for (int D = 0; D <= b[4]; D ++ )
                {
                    int t = score[A + B * 2 + C * 3 + D * 4];
                    int &v = f[A][B][C][D];
                    v = t;
                    if (A) v = max(v, f[A - 1][B][C][D] + t);
                    if (B) v = max(v, f[A][B - 1][C][D] + t);
                    if (C) v = max(v, f[A][B][C - 1][D] + t);
                    if (D) v = max(v, f[A][B][C][D - 1] + t);
                }

    printf("%d\n", f[b[1]][b[2]][b[3]][b[4]]);
    return 0;
}

25 评论

用户头像
上海STYLE   2023-02-07 20:53      9    踩      回复

一开始开了五维，多了一位表示位置，但后来发现可以用走的棋数表示位置，感觉自己是真的蠢

用户头像
acwing_93302   8个月前         踩      回复

是啊，我都想不到开几维

用户头像
chmffwn1   8个月前      3    踩      回复

一开始在定义状态的时候是直观定义 f[N][M][M][M][M]，爆内存，卡在了思考优化最后一维上。受y总每日一题讲解的启发，用short完成了最后一维的优化。现在的评测起貌似能过😄

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 351, M = 41;
short f[N][M][M][M];
int n, m;

short w[N];
int cnt[5];

short max(short a, short b) {
    if (a >= b) return a;
    else return b;
}

int main()
{
    memset(f, -0x3f, sizeof f);
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) cin >> w[i];
    for (int i = 0; i < m; i ++ ) {
        int x;
        cin >> x;
        cnt[x]++;
    }

    f[0][0][0][0] = w[0];

    for (int i = 0; i < n; i++) {
        for (int a = 0; a <= cnt[1]; a++) {
            for (int b = 0; b <= cnt[2]; b++) {
                for (int c = 0; c <= cnt[3]; c++) {
                    if (a) if (i >= 1) f[i][a][b][c] = max(f[i][a][b][c], f[i - 1][a - 1][b][c] + w[i]);
                    if (b) if (i >= 2) f[i][a][b][c] = max(f[i][a][b][c], f[i - 2][a][b - 1][c] + w[i]);
                    if (c) if (i >= 3) f[i][a][b][c] = max(f[i][a][b][c], f[i - 3][a][b][c - 1] + w[i]);
                    int d = (i - a - b * 2 - c * 3) / 4;
                    if (d) if (i >= 4) f[i][a][b][c] = max(f[i][a][b][c], f[i - 4][a][b][c] + w[i]);
                }
            }
        }
    }

    cout << f[n - 1][cnt[1]][cnt[2]][cnt[3]];
    return 0;
}
用户头像
ikaros_   2022-03-22 11:06      1    踩      回复

如果乌龟棋的步数不仅仅是1234，那又该怎么做⊙﹏⊙∥

用户头像
acwing_93302   8个月前         踩      回复

那这题就只能暴搜吧.......，因为如果有M张的话，就要搜2的M次方，m不能太大就可以直接dfs搜就行

用户头像
Henter   3个月前         踩      回复

为什么A,B,C,D从0开始而不是1？

用户头像
Henter   3个月前         踩      回复

int t = score[A + B * 2 + C * 3 + D * 4];请问这一句中，score数组里面的这个含义是什么？还有下一行&v=f[a][b][c][d]这有什么用？

用户头像
XuperMan   7个月前         踩      回复

最后答案是不是少了 +score[0]??

用户头像
鸣一YU   8个月前         踩      回复

神仙状态表示法，这没见过的，应该都想不出来

用户头像
晓月兮清风   2023-10-28 15:56         踩      回复

基础课 J2 +
提高课 S2 + / 省选 -
进阶课 省选+ / NOI / IOI/ ICPC/ 周赛++/yxc-

用户头像
冰语晨星   2022-04-27 16:42         踩      回复

您好！这种状态数组是怎么想到的呢？是多做题，然后会碰到类似的！还是有什么好的策略呢？

用户头像
有机物x   2022-05-15 11:08         踩      回复

多做题，就会碰到类似的。

用户头像
Livinfly   2021-02-23 07:57         踩      回复

状态表示怎么想到的，懵逼中qwq

用户头像
王者第一   2021-02-09 11:30         踩      回复

y总，为什么M改为120就会RE啊？

用户头像
insight21   2021-02-09 14:03         踩      回复

可能是超出空间限制了

用户头像
我要出去乱说   2021-02-09 23:37      1    踩      回复

题目说每种卡片不会超过40张，空间限制最大64兆字节，当M=40时，40^4已经有两兆字节了，120肯定爆了

用户头像
Agito555   2022-03-02 00:24    回复了 我要出去乱说 的评论         踩      回复

这里是不是还得考虑整形由4位字节存储呢？

用户头像
哈哈哈hh   2020-06-15 20:46         踩      回复

状态计算不是很理解，y总。

比如 i=2i=2，则这一类的最大分值是 f[b1,b2−1,b3,b4]+score[b1+2b2+3b3+4b4]f[b1,b2−1,b3,b4]+score[b1+2b2+3b3+4b4]。
用户头像
wjie   2020-06-20 19:33      1    踩      回复

比如说i = 2， 表示我此时的的选择步数为2的卡片，那么状态应该从f[b1,b2-1,b3,b4]转移过来，又因为此时我站在了[b1+2b2+3b3+4b4]，所以还要加上score[b1+2b2+3b3+4b4]

用户头像
yxc   2020-07-02 15:01    回复了 wjie 的评论         踩      回复

对滴。

用户头像
楚天   2020-10-29 14:39    回复了 yxc 的评论         踩      回复

y总，dp这类问题的状态定义取决于什么。我总是拿到一个dp问题，不知道怎么定义它的状态。

用户头像
YimingLi   2021-02-09 17:15    回复了 楚天 的评论         踩      回复

感觉跟贪心一样有点玄学🤣

用户头像
Link_Cut_Y   2021-09-12 18:02    回复了 楚天 的评论         踩      回复

同感！！

用户头像
Link_Cut_Y   2021-09-12 18:02    回复了 楚天 的评论         踩      回复

不会写方程，不会设状态……

用户头像
咸鱼翻身成牛马   8个月前    回复了 楚天 的评论         踩      回复

现在呢