链接：https://ac.nowcoder.com/acm/contest/20960/1026
来源：牛客网

题目描述

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

输入描述: 

	

		首先在一行中输入T,T≤10T , T \le 10T,T≤10，代表测试数据的组数。
	


	

		每组输入在第一行给出两个正整数n,m,1≤n,m≤100n, 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 
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 
2
55
162

备注: 

		

			送货时只能单次运输，若该位置需要3次，货车必须跑3次。
		


		

			即使该位置需要被送货，我们仍然可以选择该位置作为仓库。
由于从(x,y)到(x,y+1)的变化实际上是在原来总路程的基础上将x及其以前的次数和加上，加x及其以后的次数和减掉。由此可以由前面的值来推出的值。
其中涉及到区域内次数和，需要用到二维数组的前缀和来加快计算。
代码： 
#include <bits/stdc++.h>

using namespace std;

int a[102][102];
int ans_a[102][102];

int main() {
    //在读入的过程中计算到0,0位置的花费，还有前缀和。以便后面的计算
    int T;
    cin>>T;
    while (T--) {
        int n, m, k;
        int ans = 0;
        memset(a, 0, sizeof(a));
        memset(ans_a, 0, sizeof(ans_a));
        cin>>m>>n;
        for (int i=0;i<n;i++) {
            for (int j=0;j<m;j++) {
                cin>>k;
                ans += (i+j)*k;
                //记录前缀和
                a[i][j] = k;
                if (i-1>=0) a[i][j] += a[i-1][j];
                if (j-1>=0) a[i][j] += a[i][j-1];
                if (i-1>=0&&j-1>=0) a[i][j] -= a[i-1][j-1];
            }
        }
        ans_a[0][0] = ans;
        //先计算第一行的数
        for (int i=1;i<m;i++) {
            ans_a[0][i] = ans_a[0][i-1]+a[n-1][i-1]-(a[n-1][m-1]-a[n-1][i-1]);
            if (ans_a[0][i]<ans) {
                ans = ans_a[0][i];
            }
        }
        //根据第一行的数来计算剩下的数
        for (int i=1;i<n;i++) {
            for (int j=0;j<m;j++) {
                ans_a[i][j] = ans_a[i-1][j]+a[i-1][m-1]-(a[n-1][m-1]-a[i-1][m-1]);
                if (ans_a[i][j]<ans) {
                    ans = ans_a[i][j];
                }
            }
        }
        cout<<ans<<endl;
    }
    
    
    return 0;
}