Sticks

思路 怎么搜dfs(已经复原几根木棍k，上一个木棍的下标last，当前复原木棒的进度s).

AC代码

#include<bits/stdc++.h>

using namespace std;

const int N = 70;

int n,m;  //n木棍数量 
int num, len, sum;//len原来的长度，sum目前小木棍长度之和，num = sum / len;
int a[N]; //储存 木棍
bool st[N]; //标记是否用过某一小木棍

bool cmp(int a, int b) { return a > b; } 

bool dfs(int k, int last, int s)
{   

	if (k > num)return true; //所有木棍复原完成

	if (s == len)
		return dfs(k + 1, 1, 0);//完成当前木棍的复原，进行下一个

	int fail = 0;//fail记录的是最近一次尝试拼接的木棍长度。这样再回溯时就不会再尝试相同长度的木棍。 （不是很理解还）

	for (int i = last; i <= n; i++)//从last开始
	{
		if (!st[i]&&a[i]+s<=len&&fail!=a[i])//a[i]+s<=len减去不必要的搜索
		{
			st[i] = true;//标记
			if (dfs(k, i, s + a[i]))return true;
			st[i] = false;//复原

			fail = a[i];

			if (s == 0 || s + a[i] == len)return false;//（菜狗还不是很理解）
		}
	}
	return false;
}

int main()
{
	while (cin >> n && n)
	{
		memset(st, false, sizeof st);
		memset(a, 0, sizeof a);
		m = num = len = sum = 0;

		for (int i = 1; i <= n; i++)
		{
			cin >> a[i];
			sum += a[i];
		}

		sort(a + 1, a + 1 + n, cmp);


		for (len = a[1]; len <= sum / 2; len++)//保证整除并且len的长度小于sum/2 若大于则只有一根
		{
			if (sum % len)continue;

			num = sum / len;
			
			if (dfs(1, 1, 0)) {
				m = 1;
				cout << len << endl;
				break;
			}
		}
		if(!m)cout << sum << endl;
	}
	return 0;
}