解题报告

关于F:收集豆子的问题解决的讨论：

我使用的算法为：枚举+部分和

首先问题中表明任何一次操作只能移动一个豆子，每个点只能上、下、左、右进行移动，如果这里就想到用迷宫的方式来完成，那完全就被它和迷住了！我们要明确以下几点：

（1）一个位置中的豆子总是整体移动的，不可能有的移动，而有的不移动，所以整体每次移动的代价是该位置的豆子数即d[x, y]。

（2）所有位置的豆子都会集中到某一点(x, y)，所以所有位置都会向这一点集中（即移动到(x, y)，当然移动的方法不可能是由4个方向去试探，对于任何一个位置（x’, y’）其移动到(x, y)的距离一定是abs(x’-x) + abs(y’-y);

由此两个规则，我们可以得到一个枚举算法：

for x := 1 to N do

for y := 1 to N do begin

s := 0;

for x’ := 1 to N do

for y’ := 1 to N do

inc(s, (abs(x’ – x) + abs(y’ – y)) * d[x’, y’]);

if s < min then min := s;

end;

显然这个算法的时间复杂度为o(N^4)，空间复杂度为o(N^2)。当然这个时间复杂度是无法接受的。

问题出在哪里呢？第（1）中我们考虑某个位置一个一个豆子的移动慢，所以我们考虑了某个位置的整体移动。现在看来就是一个位置一个位置考虑移动还是慢！怎么办？

由于要移动到的位置是(x, y)，也就是说其它位置要移动到第X行和第y列，那么所有不在第X行的位置，全部都要移动到第X行去；同样所有不在第y列的位置全部移动到第y列去。这样我们就有了：

（3）把每行和每列看成一个整体，每次移动的不是一个位置，而是一整行、整列！所以我们保存的数据不在是一个位置的豆子数，而是每一行和每一列的豆子数！这里所需要的空间复杂度为O(2*N) = O(N);

很显然根据整行、整列移动的方法，时间复杂度显然是O(N^3)了，这个时间复杂度是可以接受的了！其枚举算法为：

注：d[1, x]表示第x行的豆子总数；d[2, y]表示第y列的豆子总数

Min := maxLongint;

For x := 1 to N do begin

Num1 := 0;

For y := 1 to N do //整行移动

inc(Num1, abs(x – y) * d[1, y]);

for y := 1 to N do begin

Num2 := 0;

For k := 1 to N do //整列移动

Inc(Num2, abs(k – y) * d[2, k]);

If min > Num1 + Num2 then min := Num1 + Num2;

end;

至此，O(N^3)完全可以解决本问题了，不过等等，还有O(N^2)的算法哦！

利用部分和算法，可以把“整行、整列”的O(N)算法改成O(1)算法！这样就把此问题的时间复杂度降成O(N^2)级的，至于部分和的问题不需要我在??嗦了！

经过一番再次思考：除输入外，解决问题的算法最终可以在线性复杂度内完成，即算法复杂度可以降低成O(N)：

由于对于整行或整列移到是相互独立的，所以可以分别从整行和整列移动中找到最小的，结果即为这两个最小值之和！相关代码如下：

其中1~7句表示行移动到第1行和列移动第1列。 D[1, i]保存的是1~i行的所有数之和，D[2, i]保存的是1~i列的所有数之和。

1)   Num1 := N * D[1, N];
2)   Num2 := N * D[2, N];
3)   for i := 1 to N - 1 do
4)   begin
5)      Dec(Num1, D[1, i]);
6)      Dec(Num2, D[2, i]);
7)   end;
8)   min1 := Num1; min2 := Num2;
9)   for i := 1 to N do
10) begin
11)   Inc(Num1, D[1, i - 1] shl 1 - D[1, N]);                      //从上一行移动到下一行，只需要修改发生变化的值
12)   Inc(Num2, D[2, i - 1] shl 1 - D[2, N]);                      //从上一列移动到下一列，也只需要修改发生变化的值
13)   if min1 > Num1 then min1 := Num1;
14)   if min2 > Num2 then min2 := Num2
15)end;
    writeln(min1 + min2);

数信学院第四届新生程序设计竞赛暨暑期集训选拔赛解题报告