链接：Link 耗时：1.825s
这道题做的可真够久的：前前后后加起来将近有两个小时，因此当 AC 的那一刻，自己心中还是挺自豪的。
事实上，这是一道复杂一点的区间型动态规划，之所以说“复杂”，是因为它的状态转移是二维的：切蛋糕既可以横切，也可以纵切。由此我想到了分治算法：
假设一个矩形它所需要切的刀数是 f，则 f 可以由组成该矩形的小矩形的 f 值决定。
因此，这个问题具有最优子结构。由于每个状态为一个矩形，因此需要 4 个维度来记录状态（及左上、右下两个顶点）。下面是横切时的状态转移方程，纵切时同理可得：
$$ \begin{aligned} f(up, down, left, right) = &\ min\{f(up, i, left, right) \\ & + f(i, down, left, right) + right - left\},i = up + 1 .. down -1 \end{aligned} $$
{$R-}
const INF = maxint div 5; //正无穷
var
f: array [0..20, 0..20, 0..20, 0..20] of integer;
cherries: array [1..500, 1..2] of integer;
map: array [0..20, 0..20] of boolean;
n, m, i, k: integer;
function min(x, y: integer): integer; inline;
begin
if x<y then exit(x) else exit(y);
end;
function cherryin(u, d, l, r: integer): integer; inline; //判断矩形内有没有樱桃
var
i, j: integer;
begin
cherryin := 0;
for i := u+1 to d do
for j := l+1 to r do
if map[i, j] then
begin
inc(cherryin);
if cherryin = 2 then exit;
end;
end;
function dp(u, d, l, r: integer): integer;
var
b: integer;
i: integer;
begin
if f[u, d, l, r] <> -1 then
exit(f[u,d , l, r]);
b := cherryin(u, d, l, r);
if b = 1 then
begin
f[u, d, l, r] := 0;
exit(0);
end;
if b = 0 then
begin
f[u, d, l, r] := INF;
exit(INF);
end;
dp := INF;
for i := u+1 to d-1 do
dp := min(dp, dp(u, i, l, r)+dp(i, d, l, r)+r-l);
for i := l+1 to r-1 do
dp := min(dp, dp(u, d, l, i)+dp(u, d, i, r)+d-u);
f[u, d, l, r] := dp;
end;
var
_: integer;
begin
assign(input, 'main.in');reset(input);
assign(output, 'main.out');rewrite(output);
_ := 0;
readln(n, m, k);
while n>0 do
begin
inc(_);
fillchar(map, sizeof(map), 0);
fillchar(f, sizeof(f), -1);
for i := 1 to k do
begin
readln(cherries[i, 1], cherries[i, 2]);
map[cherries[i, 1], cherries[i, 2]] := true;
end;
writeln('Case ',_,': ', dp(0,n,0,m));
readln(n, m, k);
end;
close(input);close(output);
end.
