[BZOJ1084/Luogu2331][SCOI2005]最大子矩阵(动态规划)

发布于 2018-02-02  6 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ1084/Luogu2331][SCOI2005]最大子矩阵(动态规划)

Description

这里有一个n*m的矩阵,请你选出其中k个子矩阵,使得这个k个子矩阵分值之和最大。注意:选出的k个子矩阵
不能相互重叠。

Http

BZOJ
Luogu

Tag

动态规划

解决思路

看到m的范围就知道是动态规划了。分\(m=1\)和\(m=2\)两种情况讨论。
先是\(m=1\)的。设\(F[i][j]\)表示前\(j\)个数中选出\(i\)个子矩阵的最大和,那么首先它可以从\(F[i][j-1]\)转移过来,这个的意思是取这一层这一次的最大,然后可以枚举一个\(k\)从\(F[i-1][k]\)转移过来。
对于\(m=2\)的则类似设\(F[i][j][k]\)表示第一列选到\(j\),第二列选到\(k\),选出\(i\)个子矩阵的最大和,那么类比\(m=1\)的转移,它首先可以从\(F[i][j-1][k]\)和\(F[i][j][k-1]\)中大的那个转移过来,再分别枚举\(pos\)小于\(j\)和小于\(k\)分别从前面转移过来,这个是表示选择其中的一列的子矩阵。最后若\(j==k\),则还可以从同时选择两行转移过来。

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ1084/Luogu2331][SCOI2005]最大子矩阵(动态规划)


HNCJ OIer 一枚