紫书习题 10-32 UVa 1414 ( 迷之规律）

看了其他人博客，貌似i个盘子的方案数满足 f[i] = f[i-1] * x + y

？？？？？？？

神来之笔

貌似没有找到严格的证明……

牛逼……

如果这样的话暴力求出x和y然后递推完事

#include<cstdio>

#include<stack>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

int s[10][2];

stack<int> st[3];

bool judge(int a, int b, int pre)

{

	if(st[a].empty() || st[a].top() == pre) return false;

	if(st[b].empty() || st[a].top() < st[b].top()) return true;

	return false;

}

int solve(int n)

{

	REP(i, 0, 3)

		while(!st[i].empty())

			st[i].pop();

	for(int i = n; i >= 1; i--) st[0].push(i);

	int ret = 0, pre = -1;

	while(1)

	{

		if(st[1].size() == n || st[2].size() == n) return ret;

		REP(i, 0, 6)

		{

			int a = s[i][0], b = s[i][1];

			if(judge(a, b, pre))

			{

				pre = st[a].top();

				st[b].push(pre);

				st[a].pop();

				ret++;

				break;

			}

		}

	}

}

int main()

{

	int n, f2, f3;

	int x, y;

	while(~scanf("%d", &n))

	{

		REP(i, 0, 6)

		{

			char str[5];

			scanf("%s", str);

			s[i][0] = str[0] - 'A';

			s[i][1] = str[1] - 'A';

		}

		f2 = solve(2); f3 = solve(3);

		x = (f3 - f2) / (f2 - 1);

	    y = f2 - x;

		long long ans = 1;

		REP(i, 2, n + 1)

			ans = ans * x + y;

		printf("%lld\n", ans);

	}

	return 0;

}

巴特西

紫书习题 10-32 UVa 1414 ( 迷之规律）

最新文章

热门文章

巴特西

紫书 习题 10-32 UVa 1414 ( 迷之规律）

最新文章

热门文章

紫书习题 10-32 UVa 1414 ( 迷之规律）