Submission #18699

#	Time	Username	Problem	Language	Result	Execution time	Memory
18699		pichulia	L 모양의 종이 자르기 (KOI15_cut)	C++98	25 / 25	156 ms	34116 KiB

cut

#include<stdio.h>
#include<algorithm>
using namespace std;
bool r[51][51][51][51];
int x[51][51][51][51];
int dp(int a, int b, int c, int d)
{
	if (r[a][b][c][d]) return x[a][b][c][d];
	r[a][b][c][d] = true;
	int res = 199999999;
	int i, j;

	if (c * d == 0)
	{
		if(a==b)return x[a][b][c][d] = 1;

		for (i = 1; i <= a/2; i++)
		{
			int cur = dp(i, b, 0, 0) + dp(a - i, b, 0, 0);
			res = min(res, cur);
		}
		for (i = 1; i <= b / 2; i++)
		{
			int cur = dp(a, i, 0, 0) + dp(a, b-i, 0, 0);
			res = min(res, cur);
		}
		return x[a][b][c][d] = res;
	}

	for (i = 1; i < a - c; i++)
	{
		int cur = dp(i, b, 0, 0) + dp(a - i, b, c, d);
		res = min(res, cur);
	}
	res = min(res, dp(a - c, b, 0, 0) + dp(c, b - d, 0, 0));
	for (i = a - c + 1; i < a; i++)
	{
		int cur = dp(i, b, i-(a-c), d) + dp(a - i, b-d, 0, 0);
		res = min(res, cur);
	}

	for (i = 1; i < b - d; i++)
	{
		int cur = dp(a, i, 0, 0) + dp(a, b - i, c, d);
		res = min(res, cur);
	}
	res = min(res, dp(a, b - d, 0, 0) + dp(a - c, d, 0, 0));
	for (i = b - d + 1; i < b; i++)
	{
		int cur = dp(a, i, c, i - (b - d)) + dp(a - c, b - i, 0, 0);
		res = min(res, cur);
	}

	return x[a][b][c][d] = res;
}
int main()
{
	int a, b, c, d;
	scanf("%d %d %d %d", &a, &b, &c, &d);
	printf("%d\n", dp(a, b, c, d));
}

• Subtask 1: 25 / 25