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

贾蔷
• 阅读 153

一、题目描述 简要描述题目:例如,在一个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时刻开始,
cpp加油站 cpp加油站
4年前
题解5道c++面试题第一期(含解题思路、答案解析和实现代码)
本篇文章送上5道c/c面试题目,并附上答案、解题思路以及扩展知识。1.求下面函数的返回值cinclude<stdio.hintfunc(intx)intiCnt0;while(x)iCnt;xx&(x1);returniCnt;intmain()printf("cnt%d\n",func(9999
Stella981 Stella981
3年前
LeetCode 92. 反转链表 II(Reverse Linked List II)
题目描述反转从位置_m_到_n_的链表。请使用一趟扫描完成反转。说明:1≤ _m_ ≤ _n_ ≤链表长度。示例:输入:12345NULL,m2,n4输出:14325NULL解题思路本题类似于反转链表
Stella981 Stella981
3年前
Codeforces997C Sky Full of Stars 【FMT】【组合数】
题目大意:一个$n\n$的格子,每个格子由你填色,有三种允许填色的方法,问有一行或者一列相同的方案数。题目分析:标题的FMT是我吓人用的。一行或一列的问题不好解决,转成它的反面,没有一行和一列相同的方案数。从一个方向入手,比如列,把一列看成一个整体。把颜色看成二进制数,$001$,$010$,$100$。那么一列构成了一个长度为$3
可莉 可莉
3年前
16. 数值的整数次方(剑指 Offer 题解Java版)
文章目录16\.数值的整数次方题目链接题目描述解题思路实现代码16\.数值的整数次方题目链接NowCoder题目描述        给定一个double类型的浮点数
贾蔷 贾蔷
3天前
2025年GESP七级等价消除(洛谷P11965)代码解析与优化策略
一、题目解读2025年GESP七级考试中的“等价消除(洛谷P11965)”问题要求统计给定字符串中满足等价条件的子串数量。所谓“等价子串”,是指子串中所有字符出现的次数均相同。题目需要高效算法解决,考验对字符串处理和状态压缩的掌握。二、解题思路采用位运算
贾蔷 贾蔷
2星期前
力扣1137题 解题思路和步骤 C++代码实现,力扣一共多少题
一、题目分析力扣1137题要求我们找到第N个泰波那契数。泰波那契数的定义是:T00,T11,T21,且在n0的条件下Tn3TnTn1Tn2。,当n4时,T4T3T2T14。这道题主要考查我们对递归或动态规划的理解和运用。在思考解题方法时,我们
贾蔷 贾蔷
3天前
蓝桥杯2023接龙数列(洛谷P9242)题解:动态规划与数字首尾匹配的完美应用
一、题目解读这道蓝桥杯省赛真题要求找出数字序列中最长的接龙子序列(每个数字的首位等于前一个数字的末位),并计算需要删除的最少数字个数。题目考察动态规划的实际应用能力,是理解数字特征处理和状态转移的典型案例。二、解题步骤1.处理n1的特殊边界情况2.读取输入
贾蔷 贾蔷
3天前
洛谷P1255题 解题思路和步骤 C++实现带注释,c++入门基础题
一、问题描述与递推关系建立洛谷P1255数楼梯问题要求计算n级台阶的不同走法数,每次可以跨1级或2级。这本质上是斐波那契数列的变种问题,递推公式为f(n)f(n1)f(n2)。当n≤50时可用普通整型存储,但题目中n可能达到5000,这就必须使用高精度运
贾蔷 贾蔷
3天前
洛谷P11228地图探险题解(CSP-J 2024真题)
一、题目重述给定n×m的二维矩阵表示探险地图,每个格子可能是:平地('.')障碍物('')起点('S')终点('E')求从起点到终点的最短路径步数,无法到达则输出1。二、核心算法:BFS广度优先搜索选择原因:BFS是解决无权图最短路径问题的最优方案,时间复