【题解】建物流中转站

我们先来回顾一下课上讲的例题5，第一章1小时09分左右开始

思路是枚举每一个子正方形。枚举正方形的方法是这样的：知道了一个正方形的左上方顶点，并且知道了这个正方形的边长，就可以确定一个正方形。
然后判断这个正方形的边上是不是全为1，如果用正常的方式来判断，还要把正方形边上的数字全部判断一遍才能得到答案。
如何判断正方形是不是符合条件做优化呢？
我们建立两个辅助数组，就表示第i行第j列往左有多少个连续的1， 表示第i行第j列往下有多少个连续的1
然后判断这个正方形是不是边长全是1就很好求了，只需要在这个数组里取一下四个值就可以通过的时间复杂度完成判断

这道题目的核心思想就是将我们需要重复求解的值先存在辅助数组里，之后计算的时候直接拿出来使用就好。

题面描述

Shopee物流会有很多个中转站。在选址的过程中，会选择离用户最近的地方建一个物流中转站。
假设给你一个二维平面网格，每个格子是房子则为1，或者是空地则为0。找到一个空地修建一个物流中转站，使得这个物流中转站到所有的房子的距离之和最小。 能修建，则返回最小的距离和。如果无法修建，则返回 -1。
若范围限制在100*100以内的网格，如何计算出最小的距离和？
当平面网格非常大的情况下，如何避免不必要的计算？

输入描述

4
0 1 1 0
1 1 0 1
0 0 1 0
0 0 0 0
先输入方阵阶数，然后逐行输入房子和空地的数据，以空格分隔。

输出描述

8
能修建，则返回最小的距离和。如果无法修建，则返回 -1。

示例1
输入

4
0 1 1 0
1 1 0 1
0 0 1 0
0 0 0 0

输出

8

示例2
输入

4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

输出

-1

如果范围限值在100*100以内，那么对于每一个格子暴力求解即可。下面我们来研究一下当平面网格非常大的情况下，如何避免不必要的计算。
假设格子的范围是m行n列
若仓库在点 (x,y) 处，若现在将仓库移动到点 (x+1,y) ，那么对于左下角为(1,1)，右上角为(x,m)的矩阵，所有点到达仓库的距离都+1，对于左下角为(x+1,m)，右上角为(n,m)的矩阵，所有点到达仓库的距离都-1.
所以我们考虑二维前缀和，暴力出仓库在(1,1)位置的答案，然后每次移动一个位置用二维前缀和来计算贡献就可以了。

例如上图中，在黑色五角星的位置建物流中转站到所有的房子的距离之和设为x，它向右移动一格，到图重红色五角星的位置，则橙色部分四个点的距离都+1.绿色部分三个点的距离都-1，所以在红色格子建仓库的距离之和为x+4-3 = x-1.

通利。如果向上或者是向下移动也是一样的

向下移动一格，上面五个房子的距离+1，下面3个房子的距离-1.假设黑色五角星位置设的距离和设为x，那么红色五角星位置的距离就是x+5-3=x+2
现在我们就遇到了一个问题，如何知道上面、下面、或者是右边有几个仓库？
如果不采用优化的话， 找一遍还是很慢.先引入一个知识点：二维前缀和

二维前缀和

我们要求一个矩阵内一个任意的子矩阵的数的和，我们就可以用二维前缀和，我们还是用DP来预处理，状态和一维前缀和差不多，只不过我们多加了一维，DP[i][j]表示（1,1）这个点与（i，j）这个点两个点分别为左上角和右下角所组成的矩阵内的数的和，好好想一下状态转移方程，DP[i][j]=DP[i-1][j]+DP[i][j-1]-DP[i-1][j-1]+map[i][j],怎么来的呢？我们画一下图就知道了。

这张图就知道了（i，j）可以由（i-1，j）和（i,j-1）两块构成，不过要注意两个点

1. 有一块矩阵我们重复加了，也就是（i-1，j-1）这一块，所以我们要减去它。
2. 我们这个矩阵是不完整的，由图可知我们还有一块深蓝色的没有加，也就是（i，j）这一点，所以我们要再加上map[i][j]也就是题目给出的矩阵中这一格的数。

这样我们就预处理完了，现在讲一下怎么通过我们的预处理从而快速地得出我们想要的任意子矩阵中的和，我们定义（x1，y1）为我们想要子矩阵的左上角，（x2，y2）为我们想要子矩阵的右下角，然后我们画图想一想。

绿色矩阵部分的和就是DP[x2][y2]-DP[x1-1][y2]-DP[x2][y1-1]+DP[x1-1][y1-1]，
二维前缀和部分图和资料参考网络
看完了二维前缀和以后，再回到之前的题目，有了二维前缀和数组，我们就可以在的时间求出矩阵中任何一个子矩阵的和。那么想知道上面或者是左边有多少个房子就很容易了
练习题:仓库选址

仓库选址

题目描述

牛能在某小城有了固定的需求，为了节省送货的费用，他决定在小城里建一个仓库，但是他不知道选在哪里，可以使得花费最小。
给出一个m \times nm×n的矩阵，代表下一年小城里各个位置对货物的需求次数。我们定义花费为货车载货运输的距离，货车只能沿着水平或竖直方向行驶。

输入描述:

首先在一行中输入T , T \le 10T,T≤10，代表测试数据的组数。
每组输入在第一行给出两个正整数n, m, 1 \le n,m \le 100n,m,1≤n,m≤100，分别代表矩阵的宽和高。
接下来m行，每行n个不超过1000的数字，代表矩阵里的元素。

输出描述:

每组输入在一行中输出答案。
示例1
输入

3
2 2
1 1
1 0
4 4
0 8 2 0
1 4 5 0
0 1 0 1
3 9 2 0
6 7
0 0 0 0 0 0
0 1 0 3 0 1
2 9 1 2 1 2
8 7 1 3 4 3
1 0 2 2 7 7
0 1 0 0 1 0
0 0 0 0 0 0

输出

2
55
162

备注:

送货时只能单次运输，若该位置需要3次，货车必须跑3次。
即使该位置需要被送货，我们仍然可以选择该位置作为仓库。