Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:参考了网上的思路,总算A了,此题真是回溯的神题啊!

Posted by 1700831 at 2018-01-21 11:01:51 on Problem 1011
In Reply To:参考了网上的思路,总算A了,此题真是回溯的神题啊! Posted by:zoujing1978 at 2017-04-08 10:59:31
> #include <iostream>
> #include <algorithm>
> using namespace std;
> 
> class Sticks
> {
> protected:
> 	int* a;
> 	int n;
> 	int sum;
> 	bool* used;
> 	bool DFS(int stickCount, int len, int index, int aim);
> public:
> 	Sticks(int n);
> 	~Sticks();
> 	void ReadData();
> 	int DFS();
> };
> 
> Sticks::Sticks(int n)
> {
> 	this->n = n;
> 	a = new int[n];
> 	used = new bool[n];
> }
> 
> Sticks::~Sticks()
> {
> 	delete[] a;
> 	delete[] used;
> }
> 
> void Sticks::ReadData()
> {
> 	sum = 0;
> 	for (int i = 0; i < n; i++)
> 	{
> 		cin >> a[i];
> 		sum += a[i];
> 	}
> }
> // stickCount:下标index(含)前已经搜索过的组合成完整的长度为aim的长棍子的数量
> // len:本次搜索已经构成的长度
> // index:要搜索下标index(不含)之后的短棍子
> // aim:目标长度
> bool Sticks::DFS(int stickCount, int len, int index, int aim)
> {
> 	if (stickCount == sum / aim)
> 	{
> 		return true;
> 	}
> 	for (int i = index + 1; i < n; i++)
> 	{
> 		if (used[i])
> 		{
> 			continue;
> 		}
> 		if (len + a[i] == aim)
> 		{
> 			used[i] = true;
> 			if (DFS(stickCount + 1, 0, -1, aim))
> 			{
> 				return true; //这里的程序结构很巧妙
> 			}
> 			used[i] = false;
> 			return false;
> 		}
> 		else if (len + a[i] < aim)
> 		{
> 			used[i] = true;
> 			if (DFS(stickCount, len + a[i], i, aim))
> 			{
> 				return true;
> 			}
> 			used[i] = false;
> 			if (len == 0)
> 			{
> 				return false;
> 			}
> 			while (a[i] == a[i + 1]) // 剪枝技巧之一
> 			{
> 				i++;
> 			}
> 		}
> 	}
> 	return false;
> }
> 
> int Sticks::DFS()
> {
> 	sort(a, a + n);
> 	reverse(a, a + n);
> 	for (int aim = a[0]; aim <= sum; aim++)
> 	{
> 		if (sum % aim == 0)
> 		{
> 			memset(used, false, sizeof(bool) * n);
> 			if (DFS(0, 0, -1, aim))
> 			{
> 				return aim;
> 			}
> 		}
> 	}
> 	return 0;
> }
> 
> int main()
> {
> 	int n = 0;
> 	cin >> n;
> 	while (n > 0)
> 	{
> 		Sticks obj(n);
> 		obj.ReadData();
> 		cout << obj.DFS() << "\n";
> 		cin >> n;
> 	}
> 	return 0;
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator