📚 第一讲：BFS进阶——带权图的最短路（可重复访问）

✅ 核心知识点

1. 传统BFS vs 本题BFS（必背对比）

2. 核心思想

当移动的代价（时间）不一样时，不能简单标记“走过”。我们需要记录每个点的当前最优解，只要新路径能得到更优解，就继续拓展。

3. 关键技术：memset赋初值（超级重点！）

memset(dist, 0x3f, sizeof dist); // 把dist数组所有元素设为无穷大

• 原理：memset是按字节赋值的函数，只能给每个字节赋相同的值
• 为什么用0x3f：
  • 一个int占4个字节，赋值0x3f后每个元素变成0x3f3f3f3f
  • 十进制约等于10亿，足够大，且两个这样的数相加不会溢出int
  • 是算法竞赛中最常用的“无穷大”写法
• ❌ 易错点：memset不能直接赋值1、10等普通数字！只能赋0、-1、0x3f

📝 完整代码模板

#include<bits/stdc++.h>
using namespace std;

// 方向数组：上下左右四个方向
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

int n, m; // 地图行数、列数
int sx, sy, ex, ey; // 起点S坐标、终点T坐标
int dist[30][30]; // dist[i][j] = 从起点到(i,j)的最少时间
char c[30][30]; // 存储地图

// 队列节点：存储坐标和到达该点的时间
struct node {
    int x, y, time;
};

int main() {
    // 1. 初始化：所有点的时间设为无穷大
    memset(dist, 0x3f, sizeof dist);
    
    // 2. 读入地图
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> c[i][j];
            if (c[i][j] == 'S') sx = i, sy = j; // 记录起点
            if (c[i][j] == 'T') ex = i, ey = j; // 记录终点
        }
    }
    
    // 3. 起点入队
    queue<node> q;
    dist[sx][sy] = 0; // 起点到自己的时间是0
    q.push({sx, sy, 0});
    
    // 4. BFS主循环
    while (!q.empty()) {
        node head = q.front(); // 取出队首元素
        q.pop(); // 弹出队首
        
        // 遍历四个方向
        for (int i = 0; i < 4; i++) {
            int nx = head.x + dx[i];
            int ny = head.y + dy[i];
            
            // 合法性判断：不越界，且不是不可通过的障碍K
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && c[nx][ny] != 'K') {
                // 计算到达新点的时间：基础移动1秒 + 特殊地形#额外1秒
                int new_time = head.time + 1 + (c[nx][ny] == '#');
                
                // ✅ 核心：如果新时间比之前记录的更短，就更新
                if (new_time < dist[nx][ny]) {
                    dist[nx][ny] = new_time; // 更新最短时间
                    q.push({nx, ny, new_time}); // 新状态入队
                }
            }
        }
    }
    
    // 5. 输出结果
    if (dist[ex][ey] == 0x3f3f3f3f) cout << -1; // 终点不可达
    else cout << dist[ex][ey]; // 输出最短时间
    
    return 0;
}

⚠️ 易错点提醒

1. ❌ 忘记初始化dist数组为无穷大，或者错误地用memset(dist, 1, sizeof dist)
2. ❌ 还在用vis数组标记访问，导致更优路径无法被找到
3. ❌ 入队条件写错：写成if (dist[nx][ny] == 0x3f3f3f3f)（只能走一次）
4. ❌ 时间计算错误：漏掉+1或者特殊地形的额外时间

🎯 重点内容

• dist数组的定义：dist[i][j]表示从起点到(i,j)的最短时间
• memset(dist, 0x3f, sizeof dist)的用法和原理
• BFS的入队条件：if (new_time < dist[nx][ny])

📚 第二讲：DP进阶——最大子矩阵和

✅ 核心知识点

1. 动态规划（DP）本质（必背）

• DP是一种用空间换时间的算法思想
• 核心：用dp数组表示某一类方案的最优结果，避免重复计算
• 关键：正确定义dp状态 + 写出正确的状态转移方程

2. 本题核心思想：降维打击

• 二维最大子矩阵和 → 转化为 → 一维最大子段和
• 暴力解法时间复杂度：$O(n^4)$（会超时）
• 优化后时间复杂度：$O(n^3)$（可以通过n=500的数据）

3. 前置知识：最大子段和（必须100%掌握）

• 问题：求一维数组中连续一段的最大和
• dp[i]定义：以第i个数结尾的最大子段和
• 状态转移方程：dp[i] = max(dp[i-1] + a[i], a[i])
  • 解释：要么接在上一段后面，要么自己重新开始一段

📝 完整代码模板

#include<bits/stdc++.h>
using namespace std;

const int INF = 1e9;
int n;
int a[510][510]; // 存储原矩阵
int s[510][510]; // 列前缀和数组
int b[510]; // 压缩后的一维数组
int dp[510]; // 最大子段和dp数组
int ans = -INF; // 最终答案，初始化为负无穷

int main() {
    cin >> n;
    
    // 1. 预处理列前缀和
    for (int i = 1; i <= n; i++) { // i是行号
        for (int j = 1; j <= n; j++) { // j是列号
            cin >> a[i][j];
            // s[j][i] = 第j列，前i行的和
            s[j][i] = s[j][i-1] + a[i][j];
        }
    }
    
    // 2. 枚举子矩阵的上下边界
    for (int i = 1; i <= n; i++) { // i：子矩阵的最上面一行
        for (int j = i; j <= n; j++) { // j：子矩阵的最下面一行
            
            // 3. 二维压缩为一维：b[k] = 第k列，从i行到j行的和
            for (int k = 1; k <= n; k++) {
                b[k] = s[k][j] - s[k][i-1];
            }
            
            // 4. 对b数组求最大子段和
            dp[0] = 0;
            for (int k = 1; k <= n; k++) {
                dp[k] = max(dp[k-1] + b[k], b[k]);
                ans = max(ans, dp[k]); // 更新全局最大值
            }
        }
    }
    
    cout << ans;
    return 0;
}

⚠️ 易错点提醒

1. ❌ 列前缀和的下标搞反：写成s[i][j] = s[i][j-1] + a[i][j]（这是行前缀和）
2. ❌ 答案初始化错误：初始化为0，当矩阵全是负数时会得到错误结果
3. ❌ 忘记重置dp数组：在每次枚举上下边界时，dp数组需要重新计算
4. ❌ 最大子段和的状态转移方程写错

🎯 重点内容

• 最大子段和的dp定义和状态转移方程
• 列前缀和的定义：s[j][i]表示第j列前i行的和
• 降维的核心步骤：枚举上下边界 → 压缩为一维数组 → 求最大子段和