方格填数

  给你一个N*N的方格，里面都是非负整数（小于32768），我们定义这个方格的总和为：其中的任何一个S*S（1<=S<=N）的子方格中的数字的总和。由于中间有K（0<=K<=N*N）个单位方格中的数字是0，因此现在给定你M（K<=M&&M<=10000）个正整数（小于32768），你可以从中选择K个，来填入原来的N*N的值为0的单位方格中，从而最大化的增加我们定义的方格的总和。

  这里有T组测试数据，第一行输入T，T<=100。对于测试数据，先输入一个N（N<=30），然后输入一个N*N的矩阵，中间含0的元素，然后给定一个M，后一行输入M个正整数。

  对于每组测试数据，输出能够最大的增加的值。

1
3
1 2 3
4 0 2
0 2 7
4
2 9 4 7

75

wangye

2008 “Insigma International Cup” Zhejiang Collegiate Programming Contest - Warm Up（4）