UVa 1629 Cake Slicing

题目

◇题目传送门◆（P.S.由于UVa较慢，这里提供一个vjudge的链接）
◇题目传送门（vjudge）◆

题目大意

给定$N,M$，表示一个矩形蛋糕的长宽。蛋糕上面有$K$个樱桃，每个樱桃都在一个单位蛋糕上。现需要将这个蛋糕分成若干块，使每块上面有且只有一个樱桃。若每刀只能沿着网格线切，且切一刀蛋糕的花费为与这一刀平行的边的长度，求最小花费。（数据保证有解）

思路

这道题似乎比较难写出状态转移方程，所以，我们可以采用记忆化搜索来做。

定义状态$f[x_1][y_1][x_2][y_2]$为左上角坐标为$(x_1,y_1)$（相对于原蛋糕的左上角），且右下角坐标为$(x_2,y_2)$的蛋糕达到目标的最小花费。

我们在记忆化搜索的时候就可以枚举切的位置，暴力找出答案。

这时我们注意到，若反复查找当前蛋糕中的樱桃个数，则可能会超时。

如何解决这个问题？

我们定义$c[x][y]$为一个以左上角为原蛋糕左上角，右下角坐标为$(x,y)$的蛋糕中的樱桃数量，计算时可以采用递推计算，具体见代码。

在计算左上角坐标为$(x_1,y_1)$（相对于原蛋糕的左上角），且右下角坐标为$(x_2,y_2)$的蛋糕中的樱桃数量时，可以使用容斥原理。举个例子：

如上图，我们计算红色部分的樱桃数量时，可先用总数（即$c[x_2][y_2]$），减掉两个紫色部分的数量，即$c[x_1-1][y_2],c[x_2][y_1-1]$（为什么要减一？因为红色部分包含了$x_1,y_1$这两个部分）。此时我们可以发现，阴影部分被减了两次，所以我们需要加上这一部分，即加上$c[x_1-1][y_1-1]$（减一的原因请见上文）。

所以，我们就可以在$O(1)$的时间计算出当前蛋糕的樱桃数量。

更多细节详见代码。

正解代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;const int Maxn=20;
const int INF=0x3f3f3f3f;int N,M,K,A[Maxn+5][Maxn+5];
int cnt[Maxn+5][Maxn+5];
int f[Maxn+5][Maxn+5][Maxn+5][Maxn+5];int DFS(int x1,int y1,int x2,int y2) {int &res=f[x1][y1][x2][y2];//定义引用，方便操作if(res!=-1) return res;int tmp=cnt[x2][y2]-cnt[x1-1][y2]-cnt[x2][y1-1]+cnt[x1-1][y1-1];//计算当前樱桃数量if(tmp==1) return 0;//已经到达目标则返回0if(tmp==0) return INF;//该蛋糕上没有樱桃，不合法，故返回INFres=INF;for(int i=y1;i<y2;i++)res=min(res,DFS(x1,y1,x2,i)+DFS(x1,i+1,x2,y2)+x2-x1+1);//竖着切for(int i=x1;i<x2;i++)res=min(res,DFS(x1,y1,i,y2)+DFS(i+1,y1,x2,y2)+y2-y1+1);//横着切return res;
}int main() {#ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifint cas=0;while(scanf("%d %d %d",&N,&M,&K)!=EOF) {for(int i=1;i<=K;i++) {int x,y;scanf("%d %d",&x,&y);A[x][y]=1;}for(int i=1;i<=N;i++)for(int j=1;j<=M;j++)cnt[i][j]=cnt[i-1][j]+cnt[i][j-1]-cnt[i-1][j-1]+A[i][j];//递推计算c数组memset(f,-1,sizeof f);//注意初值为-1printf("Case %d: %d\n",++cas,DFS(1,1,N,M));memset(cnt,0,sizeof cnt);memset(A,0,sizeof A);//清空所有数组}return 0;
}