CF208B 题解

interesting_soul_zjy · 2025-11-30 21:24:50 · 题解

CF208B 题解

题目分析

这道题是一个策略类问题，用动态规划实现。数据范围 52，显然可以 O(n^4) 实现。因为会发生变化的只有最后 3 堆牌，所以我们可以在 DP 中写四个状态：当前牌的堆数，以及最后三堆的牌的编号。

这里使用记忆化搜索实现动态规划。先预处理出所有可以合并的牌，再进行搜索。如果这个状态已经被搜索过，直接返回，否则判断两种操作方法是否能实现，并对下一步的状态进行搜索。

代码

这样说比较抽象，建议结合代码理解。

#include <iostream>
using namespace std;

string s[55];
bool flag[55][55][55][55], poker[55][55];

bool dfs(int x, int x1, int x2, int cnt)
{
    if (cnt == 1) // 如果已经合成一堆牌
    {
        return true; // 直接返回
    }
    if (flag[x][x1][x2][cnt] == true) // 记忆化，如果这个状态已经被搜索过，返回
    {
        return false;
    }
    flag[x][x1][x2][cnt] = true; // 标记这个状态已经被搜索过
    bool ans = false;
    if (poker[x][x1] == true) // 如果最右边两张牌可以合并
    {
        ans |= dfs(x, x2, cnt - 3, cnt - 1); // 更新答案
    }
    if (cnt > 3 && poker[x][cnt - 3] == true) // 如果最后一张牌和倒数第四张牌可以合并
    {
        ans |= dfs(x1, x2, x, cnt - 1); // 再次更新答案
    }
    return ans;
}

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> s[i]; // 输入
    }
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j) // 预处理
        {
            if (s[i][0] == s[j][0] || s[i][1] == s[j][1]) // 如果花色或数值相同
            {
                poker[i][j] = true; // 标记为 true
            }
        }
    }
    if (dfs(n, n - 1, n - 2, n) == true) // 通过记忆化搜索判断是否能够接龙完成
    {
        cout << "YES"; // 输出答案
    }
    else
    {
        cout << "NO";
    }

    return 0; // 完结撒花！！
}

:::success[你可以] 如果看懂了，就点个赞吧！ :::

:::warning[注意] 不要直接复制题解，会棕名的！ :::