Problem Description
A rectangular cake with a grid of m*n unit squares on its top needs to be sliced into pieces. Several cherries are scattered on the top of the cake with at most one cherry on a unit square. The slicing should follow the rules below:
1. each piece is rectangular or square;
2. each cutting edge is straight and along a grid line;
3. each piece has only one cherry on it;
4. each cut must split the cake you currently cut two separate parts
For example, assume that the cake has a grid of 3*4 unit squares on its top, and there are three cherries on the top, as shown in the figure below.
One allowable slicing is as follows.
For this way of slicing , the total length of the cutting edges is 2+4=6.
Another way of slicing is
In this case, the total length of the cutting edges is 3+2=5.
Give the shape of the cake and the scatter of the cherries , you are supposed to find
out the least total length of the cutting edges.
Input
The input file contains multiple test cases. For each test case:
The first line contains three integers , n, m and k (1≤n, m≤20), where n*m is the size of the unit square with a cherry on it . The two integers show respectively the row number and the column number of the unit square in the grid .
All integers in each line should be separated by blanks.
Output
Output an integer indicating the least total length of the cutting edges.
Sample Input
3 4 3
1 2
2 3
3 2
Sample Output
Case 1: 5
用dp[i][j][k][l]表示以(i,j)为左上角，(k,l)为右下角的矩形切成每份一个樱桃的最小切割长度。然后就利用区间DP的作用，枚举切割点，从小区间转移到大区间。由于这道题不同区间樱桃个数不同，故用区间DP的思想，递归的写法会方便些。
#include <cstdio>
#include <cmath>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
#define mst(a,b) memset((a),(b),sizeof(a))
#define rush() int T;scanf("%d",&T);while(T--)
typedef long long ll;
const int maxn = 25;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-9;
int n,m,k;
int dp[maxn][maxn][maxn][maxn];
bool flag[maxn][maxn]; //记录某个点是否有樱桃
int fun(int a,int b,int c,int d)
{
if(dp[a][b][c][d]!=-1) //已经计算过
{
return dp[a][b][c][d];
}
int cnt=0;
for(int i=a;i<=c;i++)
for(int j=b;j<=d;j++)
{
if(flag[i][j])
cnt++;
}
if(cnt<=1) //区域内樱桃个数小于2，那么不用切割
{
return dp[a][b][c][d]=0;
}
int Min=INF;
for(int i=a;i<c;i++) //横着切
{
Min=min(Min,fun(a,b,i,d)+fun(i+1,b,c,d)+(d-b+1));
}
for(int i=b;i<d;i++) //竖着切
{
Min=min(Min,fun(a,b,c,i)+fun(a,i+1,c,d)+(c-a+1));
}
return dp[a][b][c][d]=Min;
}
int main()
{
int cas=1;
int x,y;
while(~scanf("%d%d%d",&n,&m,&k))
{
mst(dp,-1);
mst(flag,0);
for(int i=0;i<k;i++)
{
scanf("%d%d",&x,&y);
flag[x][y]=1;
}
int ans=fun(1,1,n,m);
printf("Case %d: %d\n",cas++,ans);
}
return 0;
}
转自CSDN用户：Dust_Heart