题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=51190
紫书P305
题意分析：一个矩形蛋糕上有好多个樱桃，现在要做的就是切割最少的距离，切出矩形形状的小蛋糕，让每个蛋糕上都有一个樱桃,问最少切割距离是？
解题思路：既然是切割蛋糕，可以感受到是一个无限切割的过程（递归？）反正有这种感觉存在。然后数据是20*20。那么就试试记忆化搜索。我们设dp[u][d][l][r]为u(up)为上届d(down)为下界，l为左界，r为右界的最小切割距离。边界就是当整块区域只有一个樱桃显然不用切割了，返回0。当整块区域没有樱桃时，这块区域就是无效的切割，设置为无穷。
弱逼没点想法，看了大神的题解顿时恍然大悟
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
int n, m, dp[][][][];
bool has[][]; //记录格点是否有樱桃 int sum(int u, int d, int l, int r) //统计区域内的樱桃数
{
int total = ;
for(int i = u + ; i <= d; i++)
{
for(int j = l + ; j <= r; j++)
{
if(has[i][j])
total++;
if(total == ) //只要至少两个就得分割
return ;
}
}
return total;
} int dfs(int u, int d, int l, int r)
{
int &res = dp[u][d][l][r];
if(res != -)
return res;
int total = sum(u, d, l, r);
if(total == )
return res = ;
if(total == )
return res = INF;
res = INF; // 找res的最小，要先把他设成最大值
for(int i = u + ; i < d; i++)
res = min(res, dfs(u, i, l, r) + dfs(i, d, l, r) + (r - l)); //按行分割
for(int i = l + ; i < r; i++)
res = min(res, dfs(u, d, l, i) + dfs(u, d, i, r) + d - u); //按列分割
return res;
}
int main()
{
int test = ,k;
while(scanf("%d%d%d", &n, &m, &k) != EOF)
{
int x,y;
memset(has, , sizeof(has));
memset(dp, -, sizeof(dp));
for(int i = ; i < k; i++)
{
scanf("%d%d", &x, &y);
has[x][y] = ;
}
printf("Case %d: %d\n", ++test,dfs(, n, , m)); //上开下闭的区间
}
return ;
}