1.最大递增子序列和MSIS（HDU1087）

要 求出到当前位置的MSIS，我们只需要考虑所有能够到达这个位置的MSIS加上当前位置的值，取最大值即为当前位置的MSIS。

即某一个子问题会被重复计算。

// 边界条件
        for (int i = 0; i < n; i++)
        {
            dp[i] = v[i];
        }

因为本题所给元素全为正数，故只需要考虑大小，不需要考虑负影响。

能从i之前所有比他小的元素转移而来，设转移前元素为j，则

// 状态转移方程
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (v[i] > v[j])
                {
                    dp[i] = max(dp[i], dp[j] + v[i]);
                }
            }
        }

#include <iostream>

#include <vector>

#include <algorithm>
using namespace std;


int main()
{
    int n;
    while (cin >> n && n != 0)
    {
        int maxNum = 0;
        vector<int> v(n);

        // dp[i]表示以第i个元素为结尾的最大子序列和
        vector<int> dp(n, 0);
        for (int i = 0; i < n; i++)
        {
            cin >> v[i];
        }

        // 边界条件
        for (int i = 0; i < n; i++)
        {
            dp[i] = v[i];
        }

        // 状态转移方程
        for (int i = 1; i < n; i++)

        {
            for (int j = 0; j < i; j++)
            {
                if (v[i] > v[j])
                {
                    dp[i] = max(dp[i], dp[j] + v[i]);
                }
            }
        }
        for (int i = 0; i < n; i++)
        {
            maxNum = max(maxNum, dp[i]);
        }

        cout << maxNum << endl;
    }

    return 0;
}

据题意可知，本题要求在第t秒刚好到达出口。迷宫问题通常有dfs，bfs两种方法求解。由于bfs求的是最短路径，故不符合本题要求。

dfs的过程与普通迷宫问题基本相同，注意回溯

for (auto d : directions)
    {
        int newX = x + d.first;
        int newY = y + d.second;
        if (newX < 0 || newX >= n || newY < 0 || newY >= m)
            continue;
        if (visited[newX][newY])
            continue;
        if (maze[newX][newY] == 'X')
            continue;
        visited[newX][newY] = true;

        if (dfs(maze, visited, newX, newY, t - 1))
            return true;
        visited[newX][newY] = false;
    }

本题的关键在于剪枝，如果不处理会导致TLE。

剪枝的原则对应题目要求，具体有以下几种情形：

if (maze[x][y] == 'D' && t == 0)
    {
        return true;
    }
    else if (maze[x][y] == 'D' && t != 0)
    {
        return false;
    }

也可写为下方这种形式，但上述代码更为清晰。

    if (maze[x][y] == 'D')
    {
        return t == 0;
    }

注意获取S的位置，本题入口并非都为0，0.

#include <iostream>

#include <vector>

#include <algorithm>
#include <queue>
using namespace std;
vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

bool dfs(vector<vector<char>> &maze, vector<vector<bool>> &visited, int x, int y, int t)

{

    int n = maze.size();
    int m = maze[0].size();
    if (maze[x][y] == 'D')
    {
        return t == 0;
    }

    for (auto d : directions)

    {
        int newX = x + d.first;
        int newY = y + d.second;
        if (newX < 0 || newX >= n || newY < 0 || newY >= m)
            continue;
        if (visited[newX][newY])

            continue;
        if (maze[newX][newY] == 'X')
            continue;
        visited[newX][newY] = true;
        if (dfs(maze, visited, newX, newY, t - 1))
            return true;
        visited[newX][newY] = false;
    }


    return false;
}

int main()
{
    int n, m, t;
    while (cin >> n >> m >> t)
    {

        if (n == 0 && m == 0 && t == 0)
            break;
        vector<vector<char>> maze(n, vector<char>(m));

        vector<vector<bool>> visited(n, vector<bool>(m));

        int startX, startY;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                cin >> maze[i][j];
                if (maze[i][j] == 'S')
                {
                    startX = i;
                    startY = j;
                }
            }
        }

        visited[startX][startY] = true;
        if (dfs(maze, visited, startX, startY, t))
        {
            cout << "YES" << endl;
        }
        else
        {

            cout << "NO" << endl;
        }
    }

    return 0;
}

在未确定位置尝试放入未选择的数字，若与前一个数符合规则，则继续下一个位置，否则换一个数字。

这个思想对应的方法为DFS + 回溯。

注意，当n个位置全都选择好之后，还需判断第一个数字与最后一个数字的和是否为素数。

bool sumIsPrime(int a, int b)

{
    int sum = a + b;
    if (sum < 2)
        return false;

    for (int i = 2; i * i <= sum; i++)
    {
        if (sum % i == 0)
        {
            return false;
        }

    }

    return true;
}

本题要求输出所有可能的情况，且按字典序输出，因为上述dfs思路是从数字小到大搜索的，所以得出的结果也是按字典序的，只需要按序保存即可。

void dfs(vector<int> &v, vector<bool> &visited, int idx, vector<vector<int>> &solutions)

{
    int n = v.size();
    // 如果所有位置都填完
    if (idx == n)
    {
        // 最后一个位置符合要求
        if (isChecked(v, 0))
        {
            // 添加解集
            solutions.push_back(v);
        }
        return;
    }

    // 从小到大搜索
    for (int i = 2; i <= n; i++)

    {
        if (!visited[i])
        {
            v[idx] = i;
            visited[i] = true;
            // 如果符合，则继续下个位置
            if (isChecked(v, idx))
            {
                dfs(v, visited, idx + 1, solutions);
            }
            // 回溯
            visited[i] = false;
        }
    }
    return;
}

#include <iostream>

#include <vector>

#include <algorithm>
#include <queue>
using namespace std;

// 和是否为素数
bool sumIsPrime(int a, int b)
{
    int sum = a + b;
    if (sum < 2)
        return false;
    for (int i = 2; i * i <= sum; i++)
    {
        if (sum % i == 0)
        {
            return false;
        }

    }
    return true;
}


// 第idx个位置是否符合

bool isChecked(vector<int> &v, int idx)
{
    int n = v.size();
    int prev = (idx - 1 + n) % n;
    if (sumIsPrime(v[prev], v[idx]))
    {
        return true;
    }
    return false;
}

void dfs(vector<int> &v, vector<bool> &visited, int idx, vector<vector<int>> &solutions)
{
    int n = v.size();
    // 如果所有位置都填完
    if (idx == n)

    {
        // 最后一个位置符合要求
        if (isChecked(v, 0))
        {

            // 添加解集
            solutions.push_back(v);
        }
        return;
    }

    // 从小到大搜索

    for (int i = 2; i <= n; i++)
    {
        if (!visited[i])
        {

            v[idx] = i;
            visited[i] = true;
            // 如果符合，则继续下个位置
            if (isChecked(v, idx))
            {
                dfs(v, visited, idx + 1, solutions);
            }
            // 回溯
            visited[i] = false;

        }

    }

    return;
}

int main()
{
    int n;
    int caseNum = 1;

    while (cin >> n)
    {
        vector<int> v(n, 0);
        vector<bool> visited(n + 1, false);
        vector<vector<int>> solutions;
        v[0] = 1;
        visited[1] = true;
        dfs(v, visited, 1, solutions);
        if (caseNum != 1)
        {
            cout << endl;
        }
        cout << "Case " << caseNum++ << ":" << endl;
        for (auto solution : solutions)
        {
            for (int i = 0; i < n; i++)
            {
                cout << solution[i] << " ";
            }
            cout << endl;
        }
        solutions.clear();
    }
    return 0;
}

迷宫问题，题目要求找出最小时间，则考虑bfs。

本题的难点在于，不同于经典迷宫问题，该题的路径是可以重复的，所以不单单要进行访问控制，还要同时保存状态。

// dist[i][j][k]表示到达(i,j)的剩余时间为k的最短时间
vector<vector<vector<int>>> dist(n, vector<vector<int>>(m, vector<int>(7, INT_MAX)));

保存炸弹时间为k时到达i，j处的最短时间。其中k就是上文所述的“状态”。这样我们既确保了同种状态不会被多次访问，又让路径可重复。

 来进行剪枝，只要到达当前位置的不是最短时间，直接丢弃。

while (!q.empty())
        {
            state cur = q.front();
            q.pop();
            // 如果不是最短时间，则跳过，剪枝
            if (cur.time != dist[cur.x][cur.y][cur.bombtime])
            {
                continue;
            }
            // 四个方向
            for (int i = 0; i < 4; i++)
            {
                int nx = cur.x + directions[i].first;
                int ny = cur.y + directions[i].second;
                // 边界
                if (nx < 0 || nx >= n || ny < 0 || ny >= m || maze[nx][ny] == 0)
                {
                    continue;
                }


                int newtime = cur.time + 1;
                int newbombtime = cur.bombtime - 1;

                // 时间到则跳过
                if (newbombtime <= 0)
                {
                    continue;
                }

                // 到达终点
                if (maze[nx][ny] == 3)
                {
                    res = newtime;
                    while (!q.empty())
                    {
                        q.pop();
                    }
                    break;
                }

                // 更新时间
                if (maze[nx][ny] == 4)
                {
                    newbombtime = 6;
                }

                // 只有在第一次找到或找到更好的路径时才入队
                if (newtime < dist[nx][ny][newbombtime])
                {
                    dist[nx][ny][newbombtime] = newtime;
                    q.push({nx, ny, newtime, newbombtime});
                }
            }
        }


 只有在第一次找到或找到更好的路径时才入队的原因是，如果并不是最短时间也入队，则后续的操作无意义。（只保留最优解）

注意，到达终点时的break只会跳出for循环，但其实我们已经找到最后的答案，（因为bfs的特性），所以我们需要直接输出答案。

更好的做法是bfs封装成函数调用之。

#include <iostream>
#include <queue>
#include <vector>
#include <climits>
using namespace std;

// 队列元素
struct state
{
    // x,y,当前时间,剩余时间
    int x, y, time, bombtime;
};
vector<pair<int, int>> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int main()
{
    int x;
    cin >> x;
    for (int k = 0; k < x; k++)
    {
        int n, m;
        cin >> n >> m;

        // 结果，若找到，则res为最短时间，否则为-1
        int res = -1;

        vector<vector<int>> maze(n, vector<int>(m));

        // dist[i][j][k]表示到达(i,j)的剩余时间为k的最短时间
        vector<vector<vector<int>>> dist(n, vector<vector<int>>(m, vector<int>(7, INT_MAX)));
        queue<state> q;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                cin >> maze[i][j];
                if (maze[i][j] == 2)
                {
                    // 初始化队列
                    q.push({i, j, 0, 6});
                    dist[i][j][6] = 0;
                }
            }
        }
        while (!q.empty())
        {
            state cur = q.front();
            q.pop();
            // 如果不是最短时间，则跳过，剪枝
            if (cur.time != dist[cur.x][cur.y][cur.bombtime])
            {
                continue;
            }
            // 四个方向
            for (int i = 0; i < 4; i++)
            {
                int nx = cur.x + directions[i].first;
                int ny = cur.y + directions[i].second;
                // 边界
                if (nx < 0 || nx >= n || ny < 0 || ny >= m || maze[nx][ny] == 0)
                {
                    continue;
                }

                int newtime = cur.time + 1;
                int newbombtime = cur.bombtime - 1;

                // 时间到则跳过
                if (newbombtime <= 0)
                {
                    continue;
                }

                // 到达终点
                if (maze[nx][ny] == 3)
                {
                    res = newtime;
                    while (!q.empty())
                    {
                        q.pop();
                    }
                    break;
                }

                // 更新时间
                if (maze[nx][ny] == 4)
                {
                    newbombtime = 6;
                }

                // 只有在第一次找到或找到更好的路径时才入队
                if (newtime < dist[nx][ny][newbombtime])
                {
                    dist[nx][ny][newbombtime] = newtime;
                    q.push({nx, ny, newtime, newbombtime});
                }
            }
        }

        cout << res << endl;
    }

    return 0;
}

Coding day 10

数据库

详解动态规划解决最大递增子序列和(MSIS)问题，包含状态转移方程和边界条件分析。介绍DFS剪枝技巧在迷宫问题中的应用，以及BFS状态保存方法。讲解素数环问题的回溯解法，包含素数判断和字典序输出实现。提供HDU1072炸弹人问题的BFS状态保存解法，分析最优路径搜索策略。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云AI代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

功能1上新10个字符

功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符。

功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符。

功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符

功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符

功能4上新

文章&问答评论现已支持表情

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验

社区富文本编辑器全新改版！诚邀体验～ 

精选全网热门MCP server，让你的AI更好用 🚀

💥开发者 MCP广场重磅上线！

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

Coding day 10

Coding day 10

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐