NOIP 2000 提高组 洛谷1004题(方格取数)解题思路与C++代码解析

贾蔷
• 阅读 180

一、题目描述 简要描述题目:例如,在一个n×n的方格图中,每个格子包含一个正整数。需要选择两条从左上角到右下角的路径,路径可重复经过格子,但两条路径除起点和终点外不能相交。求两条路径数字和的最大值。

二、解题思路与算法分析

  1. 问题分析 1.问题核心是求解两条不交叉路径的最优组合,属于路径规划与组合优化问题。 2.直接暴力枚举路径组合的时间复杂度极高(O(2^n×n)),需采用动态规划降低复杂度。 3.关键点:如何定义状态以表示两条路径的当前位置,并确保状态转移时不交叉。
  2. 动态规划设计

(1)状态定义使用四维数组f[k][i][j]表示: k:两条路径共同走过的步数(即第k步); i:第一条路径当前所在的行坐标; j:第二条路径当前所在的列坐标。状态值f[k][i][j]为两条路径分别走到(i,j)和某个位置时的最大数字和。

(2)边界条件 初始状态:f[0][1][1] = g[1][1](两条路径均从起点(1,1)出发,数字和为起点格子值)。 其他状态初始化为负无穷(-0x3f),避免非法状态影响结果。

(3)状态转移方程分情况讨论: 当i == j时,两条路径在同一位置(重复点),只能同时向下或向右移动: (注:g[i][k+2-i]表示当前重复点的数字,因为两条路径同时移动一步。) 当i!= j时,两条路径独立移动,可分别向下或向右: (注:g[i][k+2-i]和g[j][k+2-j]分别表示两条路径当前位置的数字。) (4)最终答案:f[2*n-2][n][n](两条路径均到达右下角时的最大和)。

  1. 优化技巧 空间优化:由于状态转移仅依赖前一步的四个状态,可使用滚动数组进一步降低空间复杂度,但用户代码已通过三维数组实现(f[k][i][j]),有效避免了高维数组的存储问题。 边界处理:通过min(n, k+1)限制循环范围,避免无效计算。

三、完整代码

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

const int N = 15; 
int g[N][N], f[N*2][N][N]; 

int main() {
    int n, x, y, v;
    cin >> n; 

    while((cin >> x >> y >> v) && (x || y || v)) {
        g[x][y] = v; 
    }

    memset(f, -0x3f, sizeof f);
    f[0][1][1] = g[1][1];

    for(int k = 1; k <= 2*n-2; ++k) { 
        for(int i = 1; i <= min(n, k+1); ++i) { 
            for(int j = 1; j <= min(n, k+1); ++j) { 
                int &val = f[k][i][j]; 
                val = max({
                    f[k-1][i][j],       
                    f[k-1][i-1][j],     
                    f[k-1][i][j-1],     
                    f[k-1][i-1][j-1]   
                });
                if(i == j) val += g[i][k+2-i]; 
                else val += g[i][k+2-i] + g[j][k+2-j]; 
            }
        }
    }
    cout << f[2*n-2][n][n] << endl; 
    return 0;
}

原文:NOIP 2000 提高组 洛谷1004题(方格取数)解题思路与C++代码解析

点赞
收藏
评论区
推荐文章
Kubrnete Kubrnete
4年前
基于活动选择问题的贪心算法
目录问题描述:(问题描述%3A)输入格式(输入格式)输出格式(输出格式)算法描述(算法描述与分析)算法分析(算法分析)算法图示(图解)问题描述:Coda从0时刻开始观看直播,到t时刻结束。一共有n场直播可被选择,已知所有直播场次的起止时间和主播名称,其中第i场直播从ai时刻开始,
贾蔷 贾蔷
1个月前
力扣1137题 解题思路和步骤 C++代码实现,力扣一共多少题
一、题目分析力扣1137题要求我们找到第N个泰波那契数。泰波那契数的定义是:T00,T11,T21,且在n0的条件下Tn3TnTn1Tn2。,当n4时,T4T3T2T14。这道题主要考查我们对递归或动态规划的理解和运用。在思考解题方法时,我们
贾蔷 贾蔷
3星期前
洛谷P11228地图探险题解(CSP-J 2024真题)
一、题目重述给定n×m的二维矩阵表示探险地图,每个格子可能是:平地('.')障碍物('')起点('S')终点('E')求从起点到终点的最短路径步数,无法到达则输出1。二、核心算法:BFS广度优先搜索选择原因:BFS是解决无权图最短路径问题的最优方案,时间复
贾蔷 贾蔷
1星期前
牛客12576题全解析:动态规划+质因数分解解决跳跃问题
一、题目解读牛客12576题是一道经典的算法题,要求给定起点N和终点M,求解从N到M的最少跳跃次数。题目考察的核心在于路径优化与动态规划思想,需结合数论中的质因数分解技巧,通过合理设计算法降低时间复杂度,避免暴力枚举的指数级耗时。二、解题思路采用“动态规划
贾蔷 贾蔷
1星期前
2023年GESP六级小杨握手问题(洛谷B3874):Fenwick树求解逆序对的代码解析
一、题目解读“小杨的握手问题”源自2023年GESP六级考试(对应洛谷题目B3874)。题目描述为:给定一个长度为N的排列,每次将当前数与之前未访问过的数握手,求总共握手次数。本质上是求排列中逆序对的个数,即统计每个数右侧比它小的元素数量。需设计高效算法在
贾蔷 贾蔷
1星期前
动态规划实战:洛谷P1220关路灯问题最优解(附C++代码 AC100)
一、问题重述题目描述:在一条笔直的道路上安装了N盏路灯,每盏灯有位置和功率。老张从某起点出发,每秒移动1单位距离,经过的灯可以关闭(节省电量)。要求计算关闭所有灯的最小耗电量。二、算法解析1.问题建模这是一个典型的区间DP问题,需要考虑:位置信息处理耗电量
贾蔷 贾蔷
1星期前
牛客13279题解:利用递归与深度优先搜索计算树的最大高度(附完整代码)
一、题目解读牛客13279题要求计算给定树的最大高度。题目输入一棵以邻接表形式表示的树(节点从0开始编号),需要输出从根节点到最深叶节点的最长路径长度。树的结构由n个节点和n1条边构成,保证为连通无环图。理解题目核心在于准确获取树的拓扑关系,并设计算法遍历
贾蔷 贾蔷
1星期前
2023年GESP六级题解:洛谷P10108闯关游戏动态规划解法详解
一、题目解读本文针对2023年GESP六级题目“闯关游戏”(洛谷P10108)进行详细解析。题目要求玩家通过不同关卡路径选择,计算从起点到终点的最大得分。关卡间存在跳跃规则,需结合动态规划思想设计高效算法,最终输出最优得分。二、解题思路采用动态规划(Dyn
深度学习 深度学习
1星期前
洛谷P2034题解:动态规划+单调队列优化求解最大K段子段和问题
一、题目解读洛谷P2034题目要求给定一个长度为n的整数数组,将其分成不超过k段,求各段和的最大值。该问题属于经典动态规划问题的扩展,需结合优化技巧高效求解。二、解题思路采用动态规划单调队列优化的策略。核心思想是定义状态dp
深度学习 深度学习
1星期前
2024年蓝桥杯国赛A组题 九宫格全解析:基于BFS算法的代码实现与优化
2024年蓝桥杯国赛A组题九宫格全解析:基于BFS算法的代码实现与优化蓝桥杯国赛九宫格问题BFS算法代码解析解题步骤第1张一、题目解读2024年蓝桥杯国A的九宫格题目(对应洛谷P10578)要求通过旋转九宫格中的2x2区域,实现从初始状态到目标状态的转换,