제출 #18089

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
18089		comet	L 모양의 종이 자르기 (KOI15_cut)	C++98	25 / 25	244 ms	27508 KiB

cut

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int dp[51][51][51][51];

int f(int N,int M,int x,int y){
	if(x==0||y==0)x=y=0;
	if(x==0&&y==0){
		if(N==1)return M;
		if(M==1)return N;
		if(N==M)return 1;
	}
	// if(x==N&&y==M)return 0;
	int& ret=dp[N][M][x][y];
	if(~ret)return ret;
	ret=1e9;
	// y-axis
	for(int i=1;i<=x;i++){
		ret=min(ret,f(i,M-y,0,0)+f(N-i,M,x-i,y));
	}
	for(int i=x+1;i<N;i++){
		ret=min(ret,f(i,M,x,y)+f(N-i,M,0,0));
	}
	// x-axis
	for(int i=1;i<M-y;i++){
		ret=min(ret,f(N,i,0,0)+f(N,M-i,x,y));
	}
	for(int i=M-y;i<M;i++){
		ret=min(ret,f(N,i,x,i-(M-y))+f(N-x,M-i,0,0));
	}
	return ret;
}

int main(){
	memset(dp,-1,sizeof(dp));
	int N,M,x,y;
	scanf("%d%d%d%d",&N,&M,&x,&y);
	printf("%d\n",f(N,M,x,y));
}

• Subtask 1: 25 / 25