[HOJ 117][PA 2010] 分糖果

作法：

一開始枚舉其中一個子集，這樣問題就轉化成把一個集合分成兩部分，使得兩部分的差盡量少。而如果直接作的話會TLE，要用切一半的方法弄才會過。

這題好像也可以直接把要求的東西切一半，不用枚舉其中一個子集，但我沒想怎麼作@@

code :

#include<bits/stdc++.h>
#define LL long long
#define INF (1LL<<60)
#define F first
#define S second
#define mkp(x,y) make_pair(x,y)
#define MAX(x,y,z) max(x,max(y,z))
#define MIN(x,y,z) min(x,min(y,z))
using namespace std;
 
int a[25] ;
LL sum2 ;
 
set<LL> st ;
pair<LL,LL> solve(const vector<int> &v)
{
    int n1=v.size()/2 , n2=v.size()-n1 ;
    st.clear() ;
    pair<LL,LL> ret=mkp(0,sum2) ;
    for(int i=0;i<(1<<n1);i++)
    {
        LL s=0LL ;
        for(int j=0;j<n1;j++) if(i&(1<<j))
            s+=v[j] ;
        st.insert(s) ;
    }
 
    LL h=sum2/2 ;
    for(int i=0;i<(1<<n2);i++)
    {
        LL s=0LL ;
        for(int j=0;j<n2;j++) if(i&(1<<j))
            s+=v[j+n1] ;
        auto it=st.lower_bound(h-s) ;
        if(it!=st.end())
        {
            LL x=*it+s , y=sum2-x ;
            if(x>y) swap(x,y) ;
            if(y-x < ret.S-ret.F) ret=mkp(x,y) ;
        }
    }
    return ret ;
}
 
main()
{
    //freopen("in.txt","r",stdin) ;
    int n ; scanf("%d",&n) ;
    LL sum=0LL ;
    for(int i=0;i<n;i++) scanf("%d",&a[i]) , sum+=a[i] ;
    LL ans=INF ;
 
    for(int i=1;i<(1<<n);i++)
    {
        int bcnt=0 ;
        for(int j=0;j<n;j++) if(i&(1<<j))
            bcnt++ ;
        if(bcnt>n/3) continue ;
 
        sum2=sum ;
        vector<int> tmp ;
        for(int j=0;j<n;j++)
        {
            if(i&(1<<j)) sum2-=a[j] ;
            else tmp.push_back(a[j]) ;
        }
 
        if(abs(sum-sum2 - sum2/2) >= ans) continue ;
 
        pair<LL,LL> p=solve(tmp) ;
        LL x=p.F , y=p.S , z=sum-sum2 ;
        if(x>y) swap(x,y) ;
        if(y>z) swap(y,z) ; if(x>y) swap(x,y) ;
        ans=min(ans,z-x) ;
    }
    printf("%I64d\n",ans) ;
}