评测记录

也是看到评测记录里，先显然我没有用 nxt 数组记录第 i 根拼接失败后，下面该拼哪一根（后面第一根长度不同的）。

当然，在赛场上可能把快读快写给打错导致 CE,所以本方法仅供娱乐（但好像也没有那么娱乐，反正老老实实的写优化是最稳妥的）

另：附 250ms 极限 AC 小木棍的代码。

#include <bits/stdc++.h>
using namespace std;

const int N = 70;
int a[N], n, sum, x, m;
bool vis[N];

bool dfs(int len, int cnt, int last)
{
	if (cnt > m)  return true;
	if (len == x) return dfs(0, cnt + 1, 1);
	int f = 0;
	for (int i = last; i <= n; i++)
	{
		if (!vis[i] && len + a[i] <= x && f != a[i])
		{
			vis[i] = 1;
			if (dfs(len + a[i], cnt, i + 1)) return true;
			f = a[i];
			vis[i] = 0; 
			if (len == 0 || len + a[i] == x) return false;
		}
	}
	return false;
}

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

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch >'9')
    {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}
void write(int x)
{
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
    return;
}

int main()
{
	n = read();
	for (int i = 1; i <= n; i++) 
	{
		cin >> a[i];
		sum += a[i];
	}
	sort(a + 1, a + n + 1, cmp);
	for (x = a[1]; x <= sum >> 1; x++)
	{
		if (sum % x) continue;
		m = sum / x;
		if (dfs(0, 1, 1))
		{
			write(x);
			return 0;
		}
	}
	write(sum);
	return 0;
}