2022年4月29日 19次阅读 来源: self_disc
dls的算竞王国可以被表示为一个有 HH行和 WW列的网格,我们让 (ij)(ij)表示从北边第 ii行和从西边第 jj列的网格.最近此王国的公民希望国王能够修建一条铁路.
铁路的修建分为两个阶段:
1:从所有网格中挑选2个不同的网格,在这两个网格上分别修建一个火车站.在一个网络上修建一个火车站的代价是 Aij;
dls的愿望是希望用最少的花费去修建一条铁路造福公民们.现在请你求出这个最小花费.
第一行输入三个整数分别代表HWC
接下来H行,每行W个整数,代表Aij
二维前缀和:矩形每个元素值的和.
二位前缀最小值:矩形中每个元素值的最小值.
性质与二位前缀和类似,但又有所不同,二维前缀最小值不能求任意矩形区域的最小值,矩形的起点是固定的.此题刚好可以满足要求,利用二维前缀最小值的性质预处理在O(1)的复杂度下求出(x1,y1)的最佳位置.
那么如何预处理二维前缀最小值呢?
原文作者:self_disc