花了近2个小时终于AC，好爽。。
一道类似于最优矩阵链乘的题目，受《切木棍》那道题的启示，该题的原理也是一样的，仅仅只是变成了且面积。那么对应的也要添加维度 。
显然要完整的表示状态，最少要用四维数组。分别表示它的两个对角线顶点的坐标 。 然后横切或者纵切，递归需找更小的矩形，直到矩形内仅仅剩一个樱桃的时候返回0
那么问题就是如何高速的推断一个矩形内有多少个樱桃，于是决定再开一个数组记录这个矩形内樱桃的个数。一開始就是在这个地方超时（开了个五重循环） ，后来想到一个折中的办法，将时间复杂度分散开 。
受到高效那章求区间和的方法，我们能够先用一个二维数组求出每一行的每一个区间内樱桃的个数，这样就将时间复杂度大大减少了 。
本来以为这样会非常快，结果好像也不快，其它人在递归的时候求的樱桃个数居然也过了。
。或许是由于用记忆化搜索递归会剪掉非常多不必要的计算 。
细节參见代码：
#include<bits/stdc++.h>
using namespace std;
const int INF = 1000000;
int n,m,k,maxn = 0,d[22][22][22][22],cnt[22][22][22][22],f[22][22];
struct point{
int x,y;
}c[405];
int dp(int ux,int uy,int dx,int dy) {
int& ans = d[ux][uy][dx][dy];
if(cnt[ux][uy][dx][dy] == 1) return 0;//递归边界
if(ans >= 0) return ans;
ans = INF;
if(uy != dy) for(int i=uy;i<=dy;i++) { //纵切
if(cnt[ux][uy][dx][i]>0 && cnt[ux][i][dx][dy]>0)
ans = min(ans,dp(ux,uy,dx,i)+dp(ux,i+1,dx,dy) + dx - ux + 1);
}
if(ux != dx) for(int i=ux;i<=dx;i++) { //横切
if(cnt[ux][uy][i][dy]>0 && cnt[i][uy][dx][dy]>0)
ans = min(ans,dp(i+1,uy,dx,dy) + dp(ux,uy,i,dy) + dy - uy + 1);
}
return ans;
}
void init() {
for(int i=1;i<=k;i++) {
for(int r=1;r<=n;r++) {
for(int j=1;j<=m;j++) {//先求出每一行的樱桃个数
if(c[i].x == r && c[i].y <= j) f[r][j]++;
}
}
}
for(int ux=1;ux<=n;ux++) {
for(int uy=1;uy<=m;uy++) {
for(int dx=ux;dx<=n;dx++) {
for(int dy=uy;dy<=m;dy++) {
int v = 0;
for(int i=ux;i<=dx;i++) {
v += f[i][dy] - f[i][uy-1]; //分别求出一部分答案。将时间复杂度分散
}
cnt[ux][uy][dx][dy] = v;
}
}
}
}
}
int main() {
while(~scanf("%d%d%d",&n,&m,&k)) {
memset(f,0,sizeof(f));
memset(d,-1,sizeof(d));
memset(cnt,0,sizeof(cnt));
for(int i=1;i<=k;i++) scanf("%d%d",&c[i].x,&c[i].y);
init();
printf("Case %d: %d
",++maxn,dp(1,1,n,m));
}
return 0;
}