洛谷P1120 小木棍 ［数据加强版］

3个月前写过一遍，现在回来复习。当时自己写暴力好像只有10几分，现在自己写剪枝有54分，再加上一个优化就可以过了

剪枝策略：

①把木棍降序排列，因为长度短的木棍可以组成大的木棍，而大的木棍无法拆分成小的木棍。由于每个木棍都得拼上，如果先小后大，导致好几个小的加起来等于某一个大的，这样就可能让失败状态搜索树拓展两次。所以优先拼大木棍状态数减少。

②拼每一根木棍时记录已经失败的长度。由于小木棍的长度可能相同，对每个长度只搜索一次

③就是少了这一点没能过。if (mu[i] + now == len || now == 0)return;对于这种失败情况，可以直接return，因为len-mu[i]这个长度不管怎么拼之后都是失败的

#include
#include
#include

using namespace std;
const int inf = 1e9;
const int maxn = 1e5 + 10;
int n, sum = 0, maxmu = 0;
int mu[70];
int used[70];

void dfs(int now,int cnt,int last,int len)
{
	if (now == len)
	{
		dfs(0, cnt + 1, 1, len);
		return;
	}
	if (cnt == sum / len)
	{
		cout << len;
		exit(0);
	}
	int fail = 0;
	for (int i = last; i <= n; i++)
	{
		if (mu[i] == fail)continue;
		if (!used[i] && now + mu[i] <= len)
		{
			used[i] = 1;
			dfs(now + mu[i], cnt, i + 1, len);
			used[i] = 0;
			fail = mu[i];
			if (mu[i] + now == len || now == 0)return;
		}
	}
}

bool cmp(int x, int y)
{
	return x > y;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> mu[i];
		if (mu[i] > 50)n--, i--;
		else { 
			sum += mu[i]; 
			maxmu = max(maxmu, mu[i]);
		}
	}
	sort(mu + 1, mu + n + 1, cmp);
	for (int i = maxmu; i <= sum; i++)
	{
		if (sum % i)continue;
		dfs(0, 0, 1, i);
	}
	return 0;
}