UVa 1629 - Cake slicing

제목: n*m 크기의 케이크는 n*m 구역으로 나뉘는데 그중 k구역 위에 체리가 있다.너는 케이크를 k로 잘라야 한다. 각 케이크는 체리가 있는데, 잘라낼 때 수평 또는 수직으로 그물선을 따라 잘라서 끝까지 잘라야 한다.가장 짧게 자른 길이가 얼마냐고 물었다.
아이디어: DP.DP[u][d][l][r].u,d,l,r는 전체 케이크의 상하 정도를 나타낸다.큰 케이크 한 조각의 가장 좋은 절단법도 반드시 두 조각으로 나뉘어진 후의 가장 좋은 절단법이다. 각 절단법의 기억화 검색을 매거하면 풀 수 있다.상태 이동 방정식 코드 참조.

#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <memory.h>
#include <vector>
#include <queue>
#include <stack>
#include <ctype.h>
#define INF 1000000
using namespace std;


bool map[22][22];
int DP[22][22][22][22];
int n,m,k;

int judge(int u,int d,int l,int r){//          ，2     
	int re=0;
	for(int i=u+1;i<=d;i++){
		for(int j=l+1;j<=r;j++){
			if(map[i][j]){
				re++;
				if(re==2)return 2;
			}
		}
	}
	return re;
}

int fun(int u,int d,int l,int r){
	if(DP[u][d][l][r]!=-1)return DP[u][d][l][r];
	if(judge(u,d,l,r)==1){
		DP[u][d][l][r]=0;
		return 0;
	}
	if(!judge(u,d,l,r)){
		DP[u][d][l][r]=INF;
		return INF;
	}
	int re=INF;
	for(int i=u+1;i<d;i++){//   
		re=min(re,fun(u,i,l,r)+fun(i,d,l,r)+r-l);
	}
	for(int i=l+1;i<r;i++){//   
		re=min(re,fun(u,d,l,i)+fun(u,d,i,r)+d-u);
	}
	DP[u][d][l][r]=re;
	return re;
}

int main(){
	int c=1;
	while(cin>>n>>m>>k){
		memset(DP,-1,sizeof(DP));
		memset(map,0,sizeof(map));
		int nn,mm;
		for(int i=1;i<=k;i++){
			cin>>nn>>mm;
			map[nn][mm]=1;
		}
		cout<<"Case "<<c<<": "<<fun(0,n,0,m)<<endl;
		c++;
	}
	return 0;
}