紫书习题7-14 UVa 307(暴搜+剪枝)

这道题一开始我想的是在排序之后只在头和尾往中间靠近来找木块，然后就WA，事实证明这种方法是错误的。

然后参考了别人的博客。发现别人是直接暴搜，但是加了很多剪枝，所以不会超时。

我也想过这个做法，但是因为觉得肯定超时所以没有写，我显然没有想到可以这么剪枝

#include<cstdio>

#include<cstring>

#include<functional>

#include<algorithm>

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

using namespace std;

const int MAXN = 1123;

int a[MAXN], vis[MAXN], sum, n, start;

bool dfs(int cnt, int pos, int sum, int ans)

{

	if(cnt == n) return true;

	REP(i, pos, n)

	{

		if(vis[i]) continue;

		if(sum + a[i] < ans)

		{

			vis[i] = 1;

			if(dfs(cnt + 1, i + 1, sum + a[i], ans)) return true;

			vis[i] = 0;

			while(a[i + 1] == a[i] && i + 1 < n) i++;

		}

		else if(sum + a[i] == ans)

		{

			vis[i] = 1;

			if(dfs(cnt + 1, 0, 0, ans)) return true;

			vis[i] = 0;

			return false;

		}

		if(sum == 0) return false;

	}

	return false;

}

int main()

{

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

	{

		sum = 0;

		REP(i, 0, n)

		{

			scanf("%d", &a[i]);

			sum += a[i];

		}

		sort(a, a + n, greater<int>());

		for(int i = n; i > 0; i--)

			if(sum % i == 0 && sum / i >= a[0])

			{

				memset(vis, 0, sizeof(vis));

				if(dfs(0, 0, 0, sum / i))

				{

					printf("%d\n", sum / i);

					break;

				}

			}

	}

	return 0;

}

巴特西

紫书习题7-14 UVa 307(暴搜+剪枝)

最新文章

热门文章

巴特西

紫书 习题7-14 UVa 307(暴搜+剪枝)

最新文章

热门文章

紫书习题7-14 UVa 307(暴搜+剪枝)