• 今年的程序设计题只有 2 道 15 分的题，题量和代码量比 22 年少，难度也不及 22 年，很多同学觉得难要么是平时编程题练习的量不足，要么是 ds 部分花了太多时间留给编程题的时间不足。不过 25 编程题的难度也仅次于 22 年的。25 的ds 部分据说是史上最难。
• 就比如这个第二题，是非常经典的一道 dp，相信不少备考充分的同学都是刷到过类似的题目的，甚至说语法基础课的【AcWing 822. 走方格】就是这道题的简单模板，只是语法课的这道题求的是方案数，考试这道题求的是最大价值，状态转移完全一致，只是一个是加法一个是取最大，认真做过20 真题应该都会做这道题吧，915-20 编程
  ，在这篇博客的下面以及在课上都给大家提过那个 dp 问题，总结的相似例题就包含了这道类似的题目。所以你只要课上这部分认真做了是能够快速拿到这第一小问的（最大价值）。
• 至于第二小问求具体路径，思路与这块915-更改Dijkstra：求起点到终点的path数组
  完全一致，都是在更新最值的时候更新 pre 数组，课上都重点讲解过。只是这里是二维的，需要注意的细节比较多。这里不能直接在更新最值时输出坐标，因为这道题是 dp，路径是动态更新的，而且只有一条路径，所以用一个 pre 数组可以很好实现这一点。像 22 年那道是有多条路径，就不能简单的用 pre 来记录了。
• 编程共 2 道，第一道据说是个模拟题，我还没收到题目，第二题是个 dp 问题，这里先写第二题，第一题之后收集到题目了再写。

题目背景

在一个 m×n 的方格场地中，有一个机器人位于左上角的格子处，它每次只能向右或者向下移动一格，场地中的每个格子都放置了一定重量的物品，机器人每经过一个格子，就需要捡起该格子中的物品，携带其重量继续移动。请你帮助机器人规划一条从左上角走到右下角的路线，使得机器人在抵达右下角时所携带的总重量最大，并输出这个最大重量以及对应的行走路线。

输入格式

第一行包含两个整数 n 和 m，分别表示方格场地的行数和列数（1 <= n <= 300，1 <= m <= 300）。

接下来的 n 行，每行包含 m 个整数，第 i 行第 j 个整数 weight[i][j] 表示位于第 i 行第 j 列的格子中物品的重量（0 <= weight[i][j] <= 1000）。

输出格式

第一行输出一个整数，表示机器人从左上角走到右下角所能携带的最大总重量。

接下来若干行，每行输出一对用括号括起来的整数，表示机器人行走路线经过的格子坐标，按照从左上角到右下角的顺序输出，即先输出起点 (1,1)，最后输出终点 (n,m)。

示例

输入

3 3
2 3 1
1 7 1
4 6 1

输出

19
(1,1)
(2,2)
(3,2)
(3,3)

算法思路：运用动态规划思想，通过比较从上方和左方到达每个方格所能获得的累计值大小来更新每个方格的最大累计值，并记录路径前驱，最后借助栈回溯输出从左上角到右下角获取最大累计值的行走路径。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>

using namespace std;

const int N = 310;

// f[i][j]数组用于通过动态规划存储从左上角走到坐标(i, j)位置时能获取到的最大值
int f[N][N];    
int n;           
int m;           
// pre_x[i][j]用于记录走到坐标(i, j)位置时，上一步所在位置的横坐标，辅助回溯路径
int pre_x[N][N];  
// pre_y[i][j]用于记录走到坐标(i, j)位置时，上一步所在位置的纵坐标，辅助回溯路径
int pre_y[N][N];  

int main()
{
    cin >> n >> m;
    // 遍历方格的每一个位置，计算走到该位置时的最大累计值并记录路径前驱坐标
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> f[i][j];
            if (f[i - 1][j] > f[i][j - 1])
            {
                f[i][j] += f[i - 1][j];    
                pre_x[i][j] = i - 1;    
                pre_y[i][j] = j;    
            }
            else
            {
                f[i][j] += f[i][j - 1];    
                pre_x[i][j] = i;    
                pre_y[i][j] = j - 1;    
            }
        }
    }

    // 输出从左上角走到右下角(n, m)位置时能获取到的最大累计值
    cout << f[n][m] << endl;    

    // 创建一个栈，用于存储从右下角回溯到左上角所经过的路径坐标，以字符串形式存储
    stack<string> res;    

    // 从右下角(n, m)位置开始，沿着记录的前驱位置回溯，直到回溯到左上角的前一个位置（不包含左上角本身，因为左上角是起点）
    for (int x = n, y = m; x > 1 && y > 1; x = pre_x[x][y], y = pre_y[x][y])
    {
        string t = "(" + to_string(x) + "," + to_string(y) + ")";    
        res.push(t);    
    }
    res.push("(1,1)");    

    while (res.size())
    {
        string t = res.top();
        res.pop();
        cout << t << endl;
    }

    return 0;
}

如果能力/时间有限，这个第一问的最大价值代码还是挺短的，性价比比较高，第二问求具体路径写个思路就行，思路很简单，还是像上面那样写就可以。这样也是能拿挺多分的。

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

using namespace std;

const int N = 310;

// f[i][j]数组用于通过动态规划存储从左上角走到坐标(i, j)位置时能获取到的最大价值
int f[N][N];    
int n;           
int m;           

int main()
{
    cin >> n >> m;
    // 遍历方格的每一个位置，计算走到该位置时的最大价值
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> f[i][j];
            // 当前位置(i, j)的最大价值等于自身价值加上从上方(i - 1, j)和左方(i, j - 1)位置能获取到的最大价值
            f[i][j] += max(f[i - 1][j], f[i][j - 1]);    
        }
    }

    // 输出从左上角走到右下角(n, m)位置时能获取到的最大价值
    cout << f[n][m] << endl;    
    return 0;
}

第一题：求1到N中的所有幸运数

一、题目描述

给定一个正整数 $N$，求1到$N$之间的所有幸运数。

二、幸运数的定义

• 初始化时，从1开始列出1到$N$的所有整数，例如当$N = 25$时，初始序列为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。下标从 1 开始。
• 1是第一个幸运数，将序列中下标为所有2的倍数的位置上的元素删除，得到新序列1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25。
• 3是第二个幸运数，将新序列中所有下标为3的倍数的位置上的元素删除，得到1, 3，7, 9, 13, 15, 19, 21, 25。删的5 11 17 23。
• 7是第三个幸运数，将新序列中所有7的倍数删除，删19。
• 剩1 3 7 9 13 15 21 25。然后9是幸运数，没东西删了，结束。

三、输入格式

输入一个正整数 $N$（$1 \leq N \leq 1000$）。

四、输出格式

输出1到$N$之间的所有幸运数，每个数占一行。

五、示例

输入

25

输出

1
3
7
9
13
15
21
25