P1120 小木棍 ［数据加强版］

 1 #include<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 int s[66];
 7 int n;
 8 int nextval[66];
 9 int sum;
10 int l;
11 int len;
12 bool flag;
13 bool used[66];
14 
15 void dfs(int num, int last, int m)
16 {
17     if (!m)
18     {
19         if (l == num)
20         {
21             flag = true;
22             return;
23         }
24         for (int i = 1; i <= n; i++)
25         {
26             if (!used[i])
27             {
28                 used[i] = true;
29                 dfs(num + 1, i, len - s[i]);
30                 used[i] = false;
31                 if (flag) return;
32                 break;
33             }
34         }
35     }
36     int left = last + 1;
37     int right = n;
38     int mid;
39     while (left < right)
40     {
41         mid = (right + left) / 2;
42         if (s[mid] <= m) right = mid;
43         else left = mid + 1;
44     }
45     for (int i = left; i <= n; i++)
46     {
47         if (!used[i])
48         {
49             used[i] = true;
50             dfs(num, i, m - s[i]);
51             used[i] = false;
52             if (flag) return;
53             if (m == s[i] || m == len) return;
54             i = nextval[i];
55             if (i == n) return;
56         }
57     }
58 }
59 
60 int main()
61 {
62     cin >> n;
63     for (int i = 1; i <= n; i++)
64     {
65         cin >> s[i];
66         if (s[i] > 50)
67         {
68             n--;
69             i--;
70             continue;
71         }
72         sum += s[i];
73     }
74     sort(s + 1, s + n + 1, greater<int>());
75     for (int i = n; i > 0; i--)
76     {
77         if (s[i] == s[i + 1]) nextval[i] = nextval[i + 1];
78         else nextval[i] = i;
79     }
80     for (len = s[1]; len <= sum / 2; len++)
81     {
82         if (sum % len) continue;
83         l = sum / len;
84         flag = false;
85         used[1] = true;
86         dfs(1, 1, len - s[1]);
87         used[1] = false;
88         if (flag)
89         {
90             cout << len;
91             return 0;
92         }
93     }
94     cout << sum;
95 }