题目链接
题目大意：一个矩形蛋糕上有好多个樱桃，现在要做的就是切割最少的距离，切出矩形形状的小蛋糕，让每个蛋糕上都有一个樱桃~问最少切割距离是？
解题报告：
因为要分开处理切开的每块蛋糕，所以我们可以想到用(r,c,w,h)来表示每个子矩阵。其中人 r,c 代表矩阵左上角的坐标，w代表矩阵的宽，h代表矩阵的长。 dp[r][c][w][h]代表该矩阵切割的最小代价。我们可以枚举横着切／竖着切的每刀的代价。 预处理出每个矩阵的樱桃个数。用前缀和思想算出每个矩阵的樱桃个数（这里需要预处理）。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 25;
int dp[maxn][maxn][maxn][maxn];
int be[maxn][maxn], val[maxn][maxn];int chk(int r, int c, int w, int h){return val[r][c]-val[r+h][c]-val[r][c+w]+val[r+h][c+w];
}int dfs(int r, int c, int w, int h){int &ans = dp[r][c][w][h];if( ans!=-1 ) return ans;if( chk(r,c,w,h)==1 ) return ans=0;if( chk(r,c,w,h)==0 ) return ans=0x3f3f3f3f;int tmp=0x3f3f3f3f;for ( int i=1; i<h; i++ ){if( chk(r,c,w,i) && chk(r+i,c,w,h-i) )tmp=min(tmp,dfs(r,c,w,i)+dfs(r+i,c,w,h-i)+w);}for ( int i=1; i<w; ++i ){if( chk(r,c,i,h) && chk(r,c+i,w-i,h) )tmp=min(tmp,dfs(r,c,i,h)+dfs(r,c+i,w-i,h)+h);}return ans=tmp;
}int main(){int n, m, k, T=0;while( scanf("%d%d%d", &n, &m, &k )==3 && n ){memset(dp,-1,sizeof(dp));memset(be,0,sizeof(be));memset(val,0,sizeof(val));for ( int i=1; i<=k; i++ ){int x, y;scanf("%d%d", &x, &y );x--, y--;be[x][y]=1;}for ( int i=n-1; i>=0; --i )for ( int j=m-1; j>=0; --j )val[i][j]=val[i+1][j]+val[i][j+1]-val[i+1][j+1]+be[i][j];printf("Case %d: %d\n", ++T, dfs(0,0,m,n));}
}