백준 15011: Irrational Division

https://www.acmicpc.net/problem/15011

15011번: Irrational Division

 

설명은 귀찮으니 그냥 코드로 대체......

입력이 최대 100이라서 시간복잡도가 아주 널널한 편이다. 내가 쓴 코드는 bottom up DP방식이 불가능해 어쩔 수 없이 top down 방식으로 구현했고 그래도 시간이 널널해서 통과됐다.

 

참고로 규칙이 있다고 한다. 아주 간단한 규칙이니 반례가 궁금한 사람은 직접 반례를 만들어보자.

왜 이런 규칙이 나오는지는 나도 이해하기 귀찮아서 그냥 넘어가는걸로

https://blog.csdn.net/weixin_30517001/article/details/98449761

TZOJ--5447: Irrational Division （博弈）_weixin_30517001的博客-CSDN博客

 

 

int max(int n, int m)
{
	return (n > m) ? n : m;
}

bool vis[105][105][2] = { 0 };
int dp[105][105][2] = { 0 };

int td(int m, int n, bool a)
{
	if (m * n == 0)
		return 0;
	if (m == 1 && n == 1)
		return a ? 1 : -1;
	if (vis[m][n][a])
		return dp[m][n][a];
	int k;
	if (m % 2 == 1)
		k = a ? 1 : -1;
	else
		k = 0;
	int ret = -2100000000;
	for (int i = 1;i <= n;i++)
	{
		int h = (i % 2 == 1) ? k : 0;
		ret = max(ret, h - td(n - i, m, (!a) ^ (i % 2 == 0)));
	}
	vis[m][n][a] = 1;
	dp[m][n][a] = ret;
	return ret;

}

int main()
{
	int p, q;
	scanf("%d %d", &p, &q);
	printf("%d", td(p, q, 1));
}