有基础班_day02考试

zxcvbnm

2025-07-03 15:59:19

发布于：上海

17阅读

0回复

0点赞

题目
机器人走路 2
最小路径和
古神肥波特
最大开销子字符串
知识闯关大冒险 II
石板问题（中等版）

机器人走路 2

题目大意

一个机器人位于一个 $n \times m$ 的网格左上角，只能向下或向右移动一步，终点为右下角。
网格中有障碍物，不能经过。

现在给定地图，求从起点 $(1, 1)$ 到终点 $(n, m)$ 的不同路径数，结果对 $114514$ 取模。

题意分析

本题是一个经典的带障碍物的动态规划路径计数问题。

设地图为 $a_{i,j}$ ，其中：

$a_{i,j} = 0$ 表示可以走；
$a_{i,j} = 1$ 表示障碍，不能走。

解题思路

一、状态设计

令 $dp[i][j]$ 表示从起点 $(1, 1)$ 到达位置 $(i, j)$ 的路径条数。

二、状态转移方程

若当前位置 $a_{i,j} = 1$ （是障碍），则 $dp[i][j] = 0$ ；

否则可以由上方或左方走来：

$dp[i][j] = \begin{cases} 0, & \text{如果 } a[i][j] = 1 \\ dp[i-1][j] + dp[i][j-1], & \text{否则} \end{cases}$

注意对 $114514$ 取模。

三、初始状态

起点 $(1, 1)$ 若为可通位置，则 $dp[1][1] = 1$ ；

其余位置可用上述转移公式逐行填充。

四、最终答案

输出 $dp[n][m]$ 。

时间复杂度分析

状态数为 $n \times m$ ；
每个状态转移 $O(1)$ ；

总时间复杂度为 $\boxed{O(n \times m)}$ 。

C++代码实现

#include <iostream>
using namespace std;

const int MOD = 114514;
const int MAXN = 1005;

int a[MAXN][MAXN];
int dp[MAXN][MAXN];

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

    // 读取网格（注意输入是 m 行 n 列）
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            cin >> a[i][j];

    // 初始化起点
    if (a[1][1] == 0) dp[1][1] = 1;

    // 动态规划转移
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == 1 && j == 1) continue;
            if (a[i][j] == 0) {
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD;
            }
        }
    }

    cout << dp[m][n] << endl;
    return 0;
}

最小路径和

题目大意

在一个 $n \times m$ 的网格中，每个格子包含一个非负整数 $a_{i,j}$ ，表示从该格子经过的代价。

机器人从左上角 $(1,1)$ 出发，每次只能向右或下走一步，目标是走到右下角 $(n,m)$ 。请你求出一条代价最小的路径，输出其总代价。

题意分析

状态受限于只能向右或向下；
每个位置只能从左边或上边转移来；
是典型的 二维动态规划路径代价最小值问题。

解题思路

一、状态定义

令 $dp[i][j]$ 表示走到第 $i$ 行第 $j$ 列的最小路径和。

二、状态转移方程

从左或上转移而来：

$dp[i][j] = \min(dp[i-1][j],\ dp[i][j-1]) + a[i][j]$

三、边界初始化

$dp[1][1] = a[1][1]$ ；
第一行只能从左走来： $dp[1][j] = dp[1][j-1] + a[1][j]$ ；
第一列只能从上走来： $dp[i][1] = dp[i-1][1] + a[i][1]$ 。

时间复杂度分析

状态数为 $n \times m$ ；
每个状态转移 $O(1)$ ；

因此总时间复杂度为 $\boxed{O(n \times m)}$ ，空间复杂度为 $O(n \times m)$ （可优化为 $O(m)$ ）。

代码实现（C++）

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

const int N = 1005;
int a[N][N], dp[N][N];

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

    // 输入地图代价
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];

    // 初始化 dp
    dp[1][1] = a[1][1];

    // 初始化第一行
    for (int j = 2; j <= m; j++)
        dp[1][j] = dp[1][j - 1] + a[1][j];

    // 初始化第一列
    for (int i = 2; i <= n; i++)
        dp[i][1] = dp[i - 1][1] + a[i][1];

    // 状态转移
    for (int i = 2; i <= n; i++) {
        for (int j = 2; j <= m; j++) {
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + a[i][j];
        }
    }

    cout << dp[n][m] << endl;
    return 0;
}

古神肥波特

题目大意

给定一个长度为 $n$ 的股票价格数组 $a$ ，其中 $a_i$ 表示第 $i$ 天的股价。你只能进行一次买入和一次卖出操作（卖出必须发生在买入之后），求最大可能利润。

如果无论何时买入卖出都无法盈利，输出 $0$ 。

题意分析

这是一道典型的单次股票买卖最大利润问题。

我们希望找出一段时间 $[i, j]$ ，使得 $i < j$ 且 $a_j - a_i$ 最大，答案即为该最大值。

解题思路

我们遍历价格数组，同时维护当前最低买入价，并在每一天尝试计算“若今天卖出，利润是多少”。

一、变量定义

$minPrice$ ：到当前为止的最小股价（买入价）；
$ans$ ：最大利润。

二、状态转移逻辑

遍历 $i = 1$ 到 $n$ ：

更新最低买入价：

$minPrice = \min(minPrice, a[i])$
当前卖出能得到的利润：

$profit = a[i] - minPrice$
更新最大利润：

$ans = \max(ans, profit)$

时间复杂度分析

仅需一次遍历数组；
每步操作均为 $O(1)$ ；

总时间复杂度为 $\boxed{O(n)}$ ，空间复杂度为 $\boxed{O(1)}$ 。

C++ 代码实现

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

const int N = 1e5 + 10;
int a[N];

int main() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    int minPrice = a[1];
    int ans = 0;

    for (int i = 2; i <= n; i++) {
        ans = max(ans, a[i] - minPrice); // 卖出
        minPrice = min(minPrice, a[i]);  // 更新最低买入价
    }

    cout << ans << endl;
    return 0;
}

最大开销子字符串

题目大意

给定：

一个字符串 $s$ （仅含小写字母）；
一个字符集 $chars$ ，每个字符对应一个自定义价值 $vals$ ；
字符在 $chars$ 中时价值为 $vals[i]$ ，否则为其字母序（如 'a' = 1，'b' = 2，…）；
定义某一子串的开销为其中每个字符的价值之和；
要求在所有连续子串中找出最大开销。

题意分析

要对 $s$ 中每个字符确定其价值；
然后问题转化为：求一个数组中的 最大连续子数组和（即经典的 最大子段和问题）；
可使用动态规划求解。

解题思路

一、预处理价值映射

用一个 int val[26] 数组，初始化为 'a' 到 'z' 的字母序；
然后根据输入将 $chars[i]$ 对应的值覆盖进去；
最终我们可以 $O(1)$ 得到任意字符的价值。

二、转换成数值数组 + 最大子段和

将字符串 $s$ 映射为整数数组 $v$ ，每个元素为对应字符的价值。

设 $dp_i$ 为以第 $i$ 个字符结尾的最大开销：

$dp_i = \max(dp_{i-1} + v_i, \ v_i)$

更新最大值： $ans = \max(ans, dp_i)$ 。

时间复杂度分析

预处理价值表： $O(m)$ ；
映射整个字符串为价值数组： $O(n)$ ；
最大子段和扫描： $O(n)$ ；

总时间复杂度为 $\boxed{O(n)}$ ，适用于 $n \le 10^5$ 的数据范围。

C++ 代码实现

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int val[26]; // 字符 'a'-'z' 的价值

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

    string s;
    cin >> s;

    cin >> m;
    string chars;
    cin >> chars;

    // 初始化默认价值（字母序）
    for (int i = 0; i < 26; i++)
        val[i] = i + 1;

    // 覆盖特殊字符的价值
    for (int i = 0; i < m; i++) {
        int v;
        cin >> v;
        val[chars[i] - 'a'] = v;
    }

    // 最大子段和算法
    int ans = -1e9, cur = 0;

    for (int i = 0; i < n; i++) {
        int cost = val[s[i] - 'a'];
        cur = max(cur + cost, cost);
        ans = max(ans, cur);
    }

    cout << ans << endl;
    return 0;
}

知识闯关大冒险 II

题目大意

有 $n$ 个围成一个环的关卡，每个关卡含有 $a_i$ 个知识点。你要从中选出若干个关卡来挑战，收集尽可能多的知识点，但有以下限制：

不能挑战相邻的两个关卡；
第一个和最后一个关卡也被认为是相邻的。

求你最多能收集的知识点总数。

题意分析

与一维数组版本相比，它加了一个“首尾相邻”的限制。

由于不能同时选第一个和最后一个元素，我们可以将环“断开”，分成两个线性子问题求解：

方案一：选择第一个，不能选最后一个 ⇒ 在 $a[1 \sim n-1]$ 上做非环形最大不连续子序列和；
方案二：不选第一个，可以选最后一个 ⇒ 在 $a[2 \sim n]$ 上做同样处理；

最终答案为两者中的最大值。

解题思路

状态定义

设 $dp[i]$ 表示在第 $i$ 个关卡结束时，能收集到的最大知识点数。

状态转移方程

$dp[i] = \max(dp[i-1], dp[i-2] + a[i])$

表示当前关卡要么不选（延续上一状态），要么选（加上 $i-2$ 的最优值 + 当前值）。

边界条件

$dp[1] = a[1]$
$dp[2] = \max(a[1], a[2])$

时间复杂度分析

两次线性动态规划，每次 $O(n)$ ；
总体复杂度： $\boxed{O(n)}$ ；
空间优化后空间复杂度为 $O(1)$ 。

C++ 代码实现

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

// 非环形最大不相邻子序列和
int rob(vector<int>& a, int l, int r) {
    int pre2 = 0, pre1 = 0; // dp[i-2], dp[i-1]

    for (int i = l; i <= r; i++) {
        int cur = max(pre1, pre2 + a[i]);
        pre2 = pre1;
        pre1 = cur;
    }

    return pre1;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n + 1); // 1-based

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    if (n == 1) {
        cout << a[1] << endl;
        return 0;
    }

    // 选a[1]，不能选a[n] => rob(1,n-1)
    // 不选a[1]，可以选a[n] => rob(2,n)
    int ans = max(rob(a, 1, n - 1), rob(a, 2, n));
    cout << ans << endl;
    return 0;
}

石板问题（中等版）

题目大意

你站在第 $1$ 块石板上，每次可以选择跨 $1$ 、 $2$ 或 $3$ 块石板。
问有多少种方法恰好到达第 $n$ 块石板？

题意分析

起点为第 $1$ 块石板；
每一步可跨 $1$ 、 $2$ 或 $3$ 块；
求到达第 $n$ 块石板的方案总数。

注意，题目要求恰好到达第 $n$ 块石板，因此不能超过。

解题思路

本题是斐波那契式动态规划的典型模型（可以跳 1、2、3 步）。

状态定义

令 $dp[i]$ 表示到达第 $i$ 块石板的方案数。

状态转移方程

从第 $i-1$ 、 $i-2$ 、 $i-3$ 块跳来：

$dp[i] = dp[i-1] + dp[i-2] + dp[i-3]$

边界条件

$dp[1] = 1$ ：起点；
$dp[2] = 1$ ：只能从 $1$ 跳一步；
$dp[3] = 2$ ：从 $1 \to 3$ （跳 2 步），或 $1 \to 2 \to 3$ （两次跳 1 步）。

时间复杂度分析

每个 $dp[i]$ 只依赖前 $3$ 项；
整体复杂度为 $\boxed{O(n)}$ ；
空间复杂度可优化为 $O(1)$ （滚动变量形式）。

C++代码实现

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    // 边界情况特判
    if (n == 1 || n == 2) {
        cout << 1 << endl;
        return 0;
    }
    if (n == 3) {
        cout << 2 << endl;
        return 0;
    }

    // dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
    int dp[30];
    dp[1] = 1;
    dp[2] = 1;
    dp[3] = 2;

    for (int i = 4; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
    }

    cout << dp[n] << endl;
    return 0;
}

有帮助，赞一个

去预览

0/2000

这里空空如也

机器人走路 2

题目大意

题意分析

解题思路

一、状态设计

二、状态转移方程

三、初始状态

四、最终答案

时间复杂度分析

C++代码实现

最小路径和

题目大意

题意分析

解题思路

一、状态定义

二、状态转移方程

三、边界初始化

时间复杂度分析

代码实现（C++）

古神肥波特

题目大意

题意分析

解题思路

一、变量定义

二、状态转移逻辑

时间复杂度分析

C++ 代码实现

最大开销子字符串

题目大意

题意分析

解题思路

一、预处理价值映射

二、转换成数值数组 + 最大子段和

时间复杂度分析

C++ 代码实现

知识闯关大冒险 II

题目大意

题意分析

解题思路

状态定义

状态转移方程

边界条件

时间复杂度分析

C++ 代码实现

石板问题（中等版）

题目大意

题意分析

解题思路

状态定义

状态转移方程

边界条件

时间复杂度分析

C++代码实现

热门讨论