看到10^30 就要想到折半搜索啊＝＝
大致的思路就是
枚举前n/2的情况
枚举后n/2的情况
然后对于前n/2的情况在后n/2的中进行二分查找 复杂度就解决辣！
搜索新姿势get!!!!!!：
代码如下:
/* ^^ ====== ^^
ID: meixiuxiu
PROG: test
LANG: C++11
*/
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <climits>
#include <string>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <sstream>
#include <cctype>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int ,int> pii;
#define MEM(a,b) memset(a,b,sizeof a)
#define CLR(a) memset(a,0,sizeof a);
#define pi acos(-1.0)
#define maxn 40000
#define maxv 100005
const int inf = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
vector<int> s1[31][31],s2[31][31];
ll a[35];
int main()
{
//freopen("in.txt","r",stdin);
int n;
while(cin >> n){
// cout << n << endl;
for(int i=0;i<=30;i++){
for(int j=0;j<=30;j++){
s1[i][j].clear();
s2[i][j].clear();
}
}
for(int i=0;i<n;i++){
scanf("%lld",&a[i]);
}
int mid = (n/2);
for(int i=0;i<(1<<mid);i++){
ll tot = 0;
int cnt1 = 0;
int cnt2 = 0;
for(int j=0;j<mid;j++){
if(i&(1<<j)){
tot+=a[j];
cnt1++;
}
else tot -= a[j],cnt2++;
}
s1[cnt1][cnt2].push_back(tot);
}
for(int i=0;i<=mid;i++){
for(int j=0;j<=mid;j++){
sort(s1[i][j].begin(),s1[i][j].end());
}
}
int mid1 = (n-mid);
for(int i=0;i<(1<<mid1);i++){
ll tot = 0;
int cnt1 = 0;
int cnt2 = 0;
for(int j=0;j<mid1;j++){
if(i&(1<<j)){
tot += a[j+mid];
cnt1++;
}
else tot -= a[j+mid], cnt2++;
}
s2[cnt1][cnt2].push_back(tot);
}
for(int i=0;i<=mid1;i++){
for(int j=0;j<=mid1;j++){
sort(s2[i][j].begin(),s2[i][j].end());
}
}
ll nmin = inf;
for(int i=0;i<=mid;i++){
for(int j=0;j<=mid;j++){
int s = s1[i][j].size();
for(int k=0;k<s;k++){
ll t = s1[i][j][k];
//cout << fabs(t) << endl;
if(i+j==n)nmin = min((ll)fabs(t),nmin);
int m1 = (n/2),m2 = (n-n/2);
int pos,siz;
if(i<=m1 && j<=m2 && s2[m1-1][m2-1].size()){
pos = lower_bound(s2[m1-i][m2-j].begin(),s2[m1-i][m2-j].end(),-1*t)-s2[m1-i][m2-j].begin();
siz = s2[m1-i][m2-j].size();
if(pos < siz && pos >= 0){
nmin = min(nmin,(ll)fabs(t+s2[m1-i][m2-j][pos]));
}
if(pos-1 < siz && pos-1 >=0){
nmin = min(nmin,(ll)fabs(t+s2[m1-i][m2-j][pos-1]));
}
if(pos+1 < siz && pos+1 >=0){
nmin = min(nmin,(ll)fabs(t+s2[m1-i][m2-j][pos+1]));
}
}
swap(m1,m2);
if(i<=m1 && j<=m2 && s2[m1-i][m2-j].size()){
pos = lower_bound(s2[m1-i][m2-j].begin(),s2[m1-i][m2-j].end(),-1*t)-s2[m1-i][m2-j].begin();
siz = s2[m1-i][m2-j].size();
if(pos < siz && pos >= 0){
nmin = min(nmin,(ll)fabs(t+s2[m1-i][m2-j][pos]));
}
if(pos-1 < siz && pos-1 >=0){
nmin = min(nmin,(ll)fabs(t+s2[m1-i][m2-j][pos-1]));
}
if(pos+1 < siz && pos+1 >=0){
nmin = min(nmin,(ll)fabs(t+s2[m1-i][m2-j][pos+1]));
}
}
}
}
}
printf("%lld\n",nmin);
}
return 0;
}