同上个题一样，代码相似度极高，或者说可以直接用一个模板吧
dp[i,j,p,q]表示一块长为j-i+1,宽为q-p+1,左上角在位置（i，j）上的蛋糕，dp[]表示当前状态下的最优值，然后对该块蛋糕枚举每一种切法即可
需要注意的是，需要剪掉樱桃为0的蛋糕的情况（想了半天没想明白为啥，一开始我是认为樱桃为0了就不需要切了，该状态的最优值置为0即可，可是WA。但是感觉不剪掉他在之后的情况中也能搜出来最优的状态啊，蛋疼不已）
coding+debug：2小时左右，记忆化+dp类型第2题
/*
* Author: Bingo
* Created Time: 2015/3/3 11:32:30
* File Name: uva1629.cpp
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <time.h>
using namespace std;
const int maxint = ;
int map[][];
int vis[][][][];
int dp[][][][];
int n,m,total;
int fun(int i,int j,int p,int q){
int cnt=;
for (int a=i;a<=j;a++)
for (int b=p;b<=q;b++)
if (map[a][b]) cnt++;
return cnt;
}
int dfs(int i,int j,int p,int q){
int &flag=vis[i][j][p][q];
int &res=dp[i][j][p][q];
if (flag) return res;
else if(fun(i,j,p,q)==) {flag=;res=;return res;}
else if(fun(i,j,p,q)==) {
flag=;res=maxint;return res;
}
else{
res=maxint;
for (int t=i;t<j;t++) {
res=min(res,dfs(i,t,p,q)+dfs(t+,j,p,q)+q-p+);
}
for (int t=p;t<q;t++) {
res=min(res,dfs(i,j,p,t)+dfs(i,j,t+,q)+j-i+);
}
flag=;return res;
}
}
int main () {
int T=;
while (cin>>n>>m>>total){
T++;
memset(map,,sizeof(map));
memset(vis,,sizeof(vis));
memset(dp,,sizeof(dp));
for (int i=;i<total;i++) {
int p,q;
cin>>p>>q;
p--;q--;
map[p][q]=;
}
cout<<"Case "<<T<<": ";
cout<<dfs(,n-,,m-)<<endl;
}
return ;
}