题意：
一块n×m的蛋糕上有若干个樱桃，要求切割若干次以后，每块蛋糕上有且仅有1个樱桃。求最小的切割长度。
分析：
d(u, d, l, r)表示切割矩形(u, d, l, r)所需要的最小切割长度。
我们可以枚举第一刀切割的方向和位置，在切割之前还要判断一下这一刀是否合法，防止出现切出来的某一个小块蛋糕上没有樱桃。
递归的边界就是这块矩形上只有一个樱桃的时候，那么就不能再切了。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 7 const int maxn = 21; 8 9 int n, m, k; 10 11 int a[maxn][maxn], sum[maxn][maxn]; 12 int dp[maxn][maxn][maxn][maxn]; 13 14 int tot(int u, int d, int l, int r) 15 { 16 return sum[d][r] - sum[d][l-1] - sum[u-1][r] + sum[u-1][l-1]; 17 } 18 19 int DP(int u, int d, int l, int r) 20 { 21 int& ans = dp[u][d][l][r]; 22 if(ans >= 0) return ans; 23 if(tot(u, d, l, r) == 1) return ans = 0; 24 25 ans = 1000000; 26 for(int i = u; i < d; i++) 27 { 28 if(tot(u, i, l, r) && tot(i+1, d, l, r)) 29 ans = min(ans, (r - l + 1) + DP(u, i, l, r) + DP(i+1, d, l, r)); 30 } 31 for(int i = l; i < r; i++) 32 { 33 if(tot(u, d, l, i) && tot(u, d, i+1, r)) 34 ans = min(ans, (d - u + 1) + DP(u, d, l, i) + DP(u, d, i+1, r)); 35 } 36 return ans; 37 } 38 39 int main() 40 { 41 int kase = 0; 42 while(scanf("%d%d%d", &n, &m, &k) == 3) 43 { 44 memset(a, 0, sizeof(a)); 45 memset(sum, 0, sizeof(sum)); 46 memset(dp, -1, sizeof(dp)); 47 for(int i = 0; i < k; i++) 48 { 49 int x, y; scanf("%d%d", &x, &y); 50 a[x][y] = 1; 51 } 52 for(int i = 1; i <= n; i++) 53 for(int j = 1; j <= m; j++) 54 sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + a[i][j]; 55 56 printf("Case %d: %d ", ++kase, DP(1, n, 1, m)); 57 } 58 59 return 0; 60 }