在这里插入图片描述
UVA1629
定义：
$UpperLeft$为矩形左上角，$LowerRight$为右下角。
$dp[UpperLeft.x][UpperLeft.y][LowerRight.x][LowerRight.y]$为由两组坐标确定的矩形区域最少要切割多少长度才能满足要求。
$PrefixSum[i][j]$为从(0,0)到(i,j)的矩形区域一共有多少樱桃。(用于O(1)计算出给定矩形区域内樱桃数量）。
初始化：

转移方程：

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
int n, m, k;
bool HasCherry[21][21];
int PrefixSum[22][22];
int dp[22][22][22][22];
constexpr static int inf = 0x3f3f3f3f;
struct Point {
	int x, y;
};
bool Input() {
	if (scanf("%d%d%d", &n, &m, &k) == EOF) {
		return false;
	}
	memset(HasCherry, false, sizeof(HasCherry));
	while (k--) {
		int x, y;
		scanf("%d%d", &x, &y);
		HasCherry[x][y] = true;
	}
	return true;
}
void InitPrefixSum() {
	memset(PrefixSum, 0x0, sizeof(PrefixSum));
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			PrefixSum[i][j] = PrefixSum[i - 1][j] + PrefixSum[i][j - 1] - PrefixSum[i - 1][j - 1] + HasCherry[i][j];
		}
	}
}
const int getCherryNumber(const Point& UpperLeft,const Point& LowerRight) {
	return
		PrefixSum[LowerRight.x][LowerRight.y]
		- PrefixSum[LowerRight.x][UpperLeft.y - 1]
		- PrefixSum[UpperLeft.x - 1][LowerRight.y]
		+ PrefixSum[UpperLeft.x - 1][UpperLeft.y - 1];
}
int DP(Point UpperLeft, Point LowerRight) {
	int& Ans = dp[UpperLeft.x][UpperLeft.y][LowerRight.x][LowerRight.y];
	const int&& CherryNumber = getCherryNumber(UpperLeft, LowerRight);
	//樱桃数量为0，不符合题意，返回inf
	if (!CherryNumber) {
		return Ans = inf;
	}
	//不需要切了，返回0
	else if (CherryNumber == 1) {
		return Ans = 0;
	}
	if (Ans != inf) {
		return Ans;
	}
	//横着切，枚举每一种切割方案
	for (int i = UpperLeft.x; i < LowerRight.x; ++i) {
		Ans = min(
			Ans, 
			DP(UpperLeft, { i,LowerRight.y }) 
			+ DP({ i + 1,UpperLeft.y }, LowerRight) 
			+ LowerRight.y - UpperLeft.y + 1
		);
	}
	//竖着切
	for (int i = UpperLeft.y; i < LowerRight.y; ++i) {
		Ans = min(
			Ans,
			DP(UpperLeft, { LowerRight.x,i })
			+ DP({ UpperLeft.x,i + 1 }, LowerRight)
			+ LowerRight.x - UpperLeft.x + 1
		);
	}
	return Ans;
}
int main() {
	int&& Case = 0;
	while (Input()) {
		InitPrefixSum();
		memset(dp, 0x3f, sizeof(dp));
		printf("Case %d: %d\n", ++Case, DP({ 1,1 }, { n, m }));
	}
	return 0;
}