NOIP 真题解析：[NOIP 2008 提高组-T3] 传纸条

[NOIP2008 提高组] 传纸条题目描述摘要本文是洛谷 P1006 [NOIP2008 提高组] 传纸条的题解。题目要求在 m×n 矩阵中找两条不重叠的路径一去一回使路径上同学的好心程度之和最大。核心思路是将问题转化为两条同时从左上角出发、只能向下或向右走到右下角的路径利用动态规划求解。状态定义为dp[k][x1][x2]表示走了 k 步时两条路径分别位于 x1 行和 x2 行的好感度最大值时间复杂度 O((nm)·m²)。小渊和小轩是好朋友也是同班同学他们在一起总有谈不完的话题。一次素质拓展活动中班上同学安排坐成一个m mm行n nn列的矩阵而小渊和小轩被安排在矩阵对角线的两端因此他们就无法直接交谈了。幸运的是他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里。小渊坐在矩阵的左上角坐标为( 1 , 1 ) (1,1)(1,1)小轩坐在矩阵的右下角坐标为( m , n ) (m,n)(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递从小轩传给小渊的纸条只可以向上或者向左传递。在活动进行中小渊希望给小轩传递一张纸条同时希望小轩给他回复。班里每个同学都可以帮他们传递但只会帮他们一次也就是说如果此人在小渊递给小轩纸条的时候帮忙那么在小轩递给小渊的时候就不会再帮忙反之亦然。还有一件事情需要注意全班每个同学愿意帮忙的好感度有高有低注意小渊和小轩的好心程度没有定义输入时用0 00表示可以用一个[ 0 , 100 ] [0,100][0,100]内的自然数来表示数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条即找到来回两条传递路径使得这两条路径上同学的好心程度之和最大。现在请你帮助小渊和小轩找到这样的两条路径。输入格式第一行有两个用空格隔开的整数m , n m,nm,n表示班里有m mm行n nn列。接下来的m mm行是一个m × n m \times nm×n的矩阵矩阵中第i ii行第j jj列的整数表示坐在第i ii行第j jj列的学生的好心程度。每行的n nn个整数之间用空格隔开。输出格式输出共一行一个整数表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。输入输出样例 #1输入 #13 3 0 3 9 2 8 5 5 7 0输出 #134说明/提示【数据范围】对于30 % 30\%30%的数据满足2 ≤ m , n ≤ 10 2 \le m,n \le 102≤m,n≤10。对于100 % 100\%100%的数据满足2 ≤ m , n ≤ 50 2 \le m,n \le 502≤m,n≤50。【题目来源】NOIP 2008 提高组第三题。思路要点​ 本题和 [NOIP2000 提高组] 方格取数 类似都是同时有两条路径要走由于同一时刻两条路径移动的总步数是相同的因此可以用走了多少步划分状态阶段设当前走了 k 步路径 1 走到第 x1 行则其列数可推算出来为 (k - x1 2 列)同理可求出路径 2 当前坐标x2 行 (k - x2 2 列)。​ 最外层枚举步数 k内两层分别枚举两条路径的行数 x1 和 x2进行状态转移求解。​ 求解时我们先假设会存在某个点被重复经过的情况只在第一次经过时加上其好感值下次就改为 0相当于不加而由于a[i][j] 0两条路径有重合点的情况必定不是最优的会在转移过程中被自动舍弃。状态定义​dp[k][x1][x2]: 走了 k 步的好感度最大值路径 1 走到第 x1 行 (k - x1 2 列)路径 2 走到第 x2 行 (k - x2 2 列) 。状态转移​ 第 k 步的状态由第 k-1 步转移来分四种情况讨论。第一条路径从左边转移来第二条路径从左边转移来 -dp[k-1][x1][x2];第一条路径从上方转移来第二条路径从左边转移来 -dp[k-1][x1-1][x2];第一条路径从左边转移来第二条路径从上方转移来 -dp[k-1][x1][x2-1];第一条路径从上方转移来第二条路径从上方转移来 -dp[k-1][x1-1][x2-1];方程dp[k][x1][x2] a[x1][y1] (x1 ! x2 ? a[x2][y2] : 0) max(max(dp[k-1][x1][x2], dp[k-1][x1-1][x2]),max(dp[k-1][x1][x2-1], dp[k-1][x1-1][x2-1]));参考代码#includebits/stdc.husingnamespacestd;intn,m,a[55][55],dp[110][55][55];/* dp[k][x1][x2]: 走了 k 步的好感度最大值k 最大 n m - 2 步。 路径 1 走到第 x1 行 (k - x1 2 列) 路径 2 走到第 x2 行 (k - x2 2 列) */intmain(){cinmn;for(inti1;im;i){for(intj1;jn;j){cina[i][j];}}for(intk1;knm-2;k){// 步数 k: 1 ~ n m - 2 步for(intx11;x1m;x1){// 枚举路径 1 当前走到第 x1 行for(intx21;x2m;x2){// 枚举路径 2 当前走到第 x2 行// 计算两条路径当前列数 y1y2inty1k-x12,y2k-x22;if(y11y1ny21y2n){// 合法dp[k][x1][x2]a[x1][y1](x1!x2?a[x2][y2]:0)// 重合只加一次max(max(dp[k-1][x1][x2],dp[k-1][x1-1][x2]),max(dp[k-1][x1][x2-1],dp[k-1][x1-1][x2-1]));}}}}coutdp[nm-2][m][m];return0;}