[ACM]poj 1011 Sticks

  • 2015-09-26
  • 0
  • 0

题意:中文题目
思路:深度搜索+剪枝
找到可能的长度然后深度遍历下去。
剪枝:
同长度不重复搜索
第一根无法拼成就停止搜索
AC代码:

#include<iostream>
using namespace std;
bool mark[64];
int sticks[64];
int n;
int len;
int sum = 0;
bool dfs(int start,int n_len,int dep)
{
	if (dep == n)
	{
		return true;
	}
	for (int i = start; i < n; i++)
	{ 
		if (!mark[i - 1] && sticks[i] == sticks[i - 1])
		{
			continue;
		}
		if (mark[i])
		{
			continue;
		}
		mark[i] = true;
		if (n_len + sticks[i] < len)
		{
			if (dfs(i, n_len + sticks[i], dep + 1))
			{
				return true;
			}
		}
		if (n_len + sticks[i] == len)
		{
			if (dfs(0, 0, dep + 1))
			{
				return true;
			}
		}
		mark[i] = false;
		if (n_len == 0)
		{
			break;
		}
	
	}
	return false;
	
}
int cmp(const void* a, const void* b)
{
	int *A = (int*)a;
	int *B = (int*)b;
	return *B - *A;
}
int main()
{
	while (cin >> n)
	{
		sum = 0;
		if (n == 0)
		{
			break;
		}
		for (int i = 0; i < n; i++)
		{
			cin >> sticks[i];
			sum += sticks[i];
			mark[i] = false;
		}
		qsort(sticks, n, sizeof(int), cmp);
		bool out = false;
		for (int i = sticks[0]; i <= sum; i++)
		{
			if (sum%i == 0)
			{
				len = i;
				if (dfs(0, 0, 0))
				{
					cout << len << endl;
					out = true;
					break;
				}

			}
		}
		if (!out)
		{
			cout << sum << endl;
		}
	}
	return 0;
	
}

评论

还没有任何评论,你来说两句吧