2022年弱弱的方格取数总结实用 .pdf

《2022年弱弱的方格取数总结实用 .pdf》由会员分享，可在线阅读，更多相关《2022年弱弱的方格取数总结实用 .pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、弱弱的“方格取数”总结By maxint64“方格取数”（rq314）最简单，也是最基础的一种就是在一个矩阵map（n*n）中找出一条从（1，1）到（n,n）的路径（只能向右或向下走，下同），使得处在该条路径上格子中数之和最大。可以用非常简单的DP,状态转移方程如下：fi,j=maxfi-1,j,fi,j-1+mapi,j;初始化 f1,1:=map1,1;当题目要求找到2 条从（1，1）到（n,n）的路径，被取走的格子里的数变为 0，使得在两条路径上格子中数之和最大时，就成为了“二取方格数”问题。最容易想到的就是先后做两次单条路径“方格取数”，这一算法的本质是贪心，但这是 错误的，反例如下：

2、2 8 2 0 0 0 2 8 2 贪心：第一路径：2-8-8-2(20)第二路径：2（2）总和为 22 事实上我们可以将所有的数都取完总和为 24解决“二取方格数”问题需要用到“多进程 dp”，,所谓多进程 dp其实也就是同时对 2 个或以上对象 dp,“配置魔药”(rq99)为多进程 dp 的基础习题，在二取方格数中也就是同时考虑两条路径。看了一些神牛的题解，除最暴力的枚举所有路径求最优值的暴搜外（看看就可以了，因为不会 ac 的），有两种 dp 方案：一种是4 维 的；另一种是3 维的。先说 4 维的，因为比较直观。我们令dpx1,y1,x2,y2表示第一条路径走到了（x1,y1）,第二

3、条路径走到了(x2,y2)是的最优解，可以很自然的得到状态转移方程：dpx1,y1,x2,y2=0;(x1=0)or(y1=0)or(x2=0)or(y2=0);否则令 p:=maxdpx1-1,y1,x2-1,y2,dpx1-1,y1,x2,y2-1,dpx1,y1-1,x2-1,y2,dpx1,y1-1,x2,y2-1;dpx1,y1,x2,y2=p+mapx1,y1;(x1=x2)and(y1=y2);p+mapx1,y1+mapx2,y2;else;这样，我们就可以用一个4 重循环把这个问题暴力地dp 掉-_-|这个算法在 rqoj 上是可以 ac 的，稍作修改（读入，循环边界和路径相

4、交时的处理）就可以把传纸条 也 ac 掉。不过大多数的题解多不是这样做的，因为4 维数组的空间开销太大。想要得到更优化的算法，我们需要再认真分析一下问题。现在让两条路径同时从(1,1)处出发，并同时向前延伸，那么当两条路径都已经包含 k 个方格时，两条路径的末端必同在整个矩阵的第k 条对角线上。因为对于每一条路径，向右延伸的格子数+向下延伸的格子数=k,也就是末端两个格子的纵横坐标之和=k。而在另一 bt 经典的“8 皇后”问题中，这正是判断两个皇后是否在同一对角线上的条件。所以我们只需要知道两路径末端所在的行编号名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 4 页 -x1,x

5、2以 及 两 末 端 所 在 对 角 线 编 号k，就 可 以 确 定 末 端 节 点 的 位 置（x1,k+1-x1）,(x2,k+1-x2)。很显然，路径每延伸一个格子所能得到的最优值，只与上次延伸的最优值有关，那么我们就可以以对角线划分阶段 进行 dp。至此，我们可以建立新的状态转移方程：dpx1,x2,k表示第一个路径末端在第x1 行，第二路径末端在第x2 行，且两末端同在第 k 条对角线上时的最优解，所以令 p=maxdpx1-1,x2,k-1,dpx1,x2-1,k-1,dpx1-1,x2-1,k-1,dpx1,x2,k-1 dpx1,x2,k=p+mapx1,k+1-x1;(x1

6、=x2);p+mapx1,k+1-x1+mapx2,k+1-x2;else 初始化 dp1,1,1:=map1,1;由于阶段 k 只与阶段 k-1 有关，在编程时可以用 滚动数组 进一步节省空间。-main program-dp1,1,0:=map1,1;/初始化t:=0;/用 0/1 来控制滚动数组for k:=2 to n+n-1 do /以对角线划分阶段begin t:=1-t;/控制滚动数组 for i:=1 to k do /枚举路径 1 末端所在行 for j:=1 to k do /枚举路径 2 末端所在行 begin p:=max(dpi-1,j,1-t,dpi,j-1,1-t

7、,dpi-1,j-1,1-t,dpi,j,1-t);if ij then dpi,j,t:=p+mapi,k+1-i+mapj,k+1-j else dpi,j,t:=p+mapi,k+1-i;end;/状态转移end;writeln(dpn,n,t);上面的程序还有可以优化空间：由于 i,j始终是从 1 到 k,所以被我们所计算过的区域是下图(n=5)中红色和蓝色的和（我感觉这个形状有点像B-2），黑色的 (n,n)是最后的答案。很明显，蓝色的两片“翅膀”是多余的。事实上，针对上文的代码，当kn 时，我们只需要让i,j 从(k-n+1)跑到 n 就可以了。所以，我们用 a,b两个变量控制 i

8、,j 的范围，把“翅膀”砍掉。-main program-f1,1,0:=map1,1;a:=1;b:=2;t:=0;for k:=2 to n+n-1 do begin t:=1-1;for i:=a to b do for j:=a to b do begin p:=max(dpi-1,j,1-t,dpi,j-1,1-t,dpi-1,j-1,1-t，dpi,j,1-t);if ij then dpi,j,t:=p+mapi,k+1-i+mapj,k+1-j else dpi,j,t:=p+mapi,k+1-i;end;if kn then inc(a)else inc(b);/边界控制en

9、d;writeln(dpn,n,t);以上的讨论都是基于矩阵为（n*n）形式下的，noip2008-p3 传纸条 所给的矩阵是（n*m）的形式，当用对角线划分阶段进行dp 时，我们可以用一个以c=maxn,m为边长的（c*c）形式的矩阵。由于多出来的格子值都为0，所以当路径到达这些格子时末端的值不会发生变化，所以保证了dpc,c,t为最优解。例：n=3;m=5;c=max3,5=5;当然，如果要追求完美，也同样可以通过对循环边界的控制，把蓝色的部分剪掉。-main program-f1,1,0:=ma1,1;t:=0;a:=1;b:=2;for k:=2 to c+c-1 do /c*c的矩阵

10、begin t:=1-t;名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 4 页 -for i:=a to b do for j:=a to b do begin if i=j then continue;/本题要求路径不相交fi,j,t:=max(fi-1,j-1,1-t,fi,j-1,1-t,fi-1,j,1-t,fi,j,1-t);fi,j,t:=fi,j,t+mai,k-i+maj,k-j;end;if bc then inc(b)else inc(a);/边界控制，没有剪掉蓝色为部分end;writeln(fc,c,t);vijos上有一个“三取方格数”，（p1143）

11、也就是要找到 3 条路径，使得取得的数总和最大。如果想一开始那样用3 条路径的末端坐标作为数组下标则需要6维，很繁琐，所以继续用对角线划分阶段，只需在增加一维就可以了。状态转移方程如下：令 p=max dpx1,x2,x3,k-1,dpx1-1,x2,x3,k-1,dpx1,x2-1,x3,k-1,dpx1,x2,x3-1,k-1,dpx1-1,x2-1,x3,k-1,dpx1-1,x2,x3-1,k-1,dpx1,x2-1,x3-1,k-1,dpx1-1,x2-1,x3-1,k-1;dpx1,x2,x3,k=p+mapx1,k+1-x1;(x1=x2)and(x1=x3);p+mapx1,k

12、+1-x1+mapx2,k+1-x2;(x1x2)and(x3=x1)or(x3=x2)p+mapx1,k+1-x1+mapx3,k+1-x3;(x1x3)and(x2=x1)or(x2=x3)p+mapx2,k+1-x2+mapx3,k+1-x3;(x2x3)and(x1=x2)or(x1=x3)p+mapx1,k+1-x1+mapx2,k+1-x2+mapx3,k+1-x3；(x1x2)and(x1x3)and(x2x3);由于增加了一维，每一阶段的状态,每个状态的决策也增加了。至此，我们讨论了（n*n）矩阵二取方格数/三取方格数,(n*m)矩阵二取方格数，推广到最一般的情况便是（n*m）矩阵中找 k 条路径，使得取得的数总和最大。疯狂的方格取数 vijos p1653 就是这一问题，解决它需要用到网络流（据说 dp 也可以，但是比较复杂），鄙人才疏学浅，还没有认真学习过网络流，就不乱写了。名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 4 页 -