题目大意：

　　有一个长度为n的数列，A和B两个人轮流从两端取数，B先取，A想使分数严格小于B且尽量接近B，问两人分数之差最小是多少。

思路：

　　折半搜索，先预处理出长度为part的最大差最小差，再预处理出后面一段能取到的不同差值，然后dfs，当范围等于part时，就在数组中二分查找一下。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 inline int getint() { 6     register char ch; 7     while(!isdigit(ch=getchar())); 8     register int x=ch^'0'; 9     while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');10     return x;11 }12 const int inf=0x7fffffff,_inf=-0x80000000;13 const int N=91;14 int a[N];15 int max[N][N],min[N][N],ans,n,part;16 inline void init() {17     ans=_inf;18     for(register int i=0;i<=n;i++) {19         for(register int j=0;j<=n;j++) {20             max[i][j]=_inf;21             min[i][j]=inf;22         }23     }24     for(register int i=1;i<=n;i++) {25         max[i][i-1]=min[i][i-1]=0;26     }27     for(register int i=n;i;i--) {28         for(register int j=i;j<=n;j++) {29             int l=i,r=j;30             int tmp=(a[l]>=a[r])?a[l++]:a[r--];31             max[i][j]=std::max(a[l]+max[l+1][r],a[r]+max[l][r-1])-tmp;32             min[i][j]=std::min(a[l]+min[l+1][r],a[r]+min[l][r-1])-tmp;33         }34     }35 }36 std::vector
         
           v[N];37 __gnu_cxx::hash_set
          
            s;38 void initPart2() {39 part=std::min(1,n/4);40 for(int i=1;i<=n+1-part*2;i++) {41 s.clear();42 v[i].clear();43 for(int j=0;j<1<
           
            =a[r])?a[l++]:a[r--];47 tmp+=(!(j&(1<
            

::iterator it=std::lower_bound(v[l].begin(),v[l].end(),-dif);60 if(it==v[l].begin()&&*it==-dif) return;61 if(it==v[l].end()||*it==-dif) it--;62 if(dif+*it<0) ans=std::max(ans,dif+*it);63 return;64 }65 if(dif+min[l][r]>=0) return;66 if(dif+max[l][r]<=ans) return;67 if(dif+max[l][r]<0) {68 ans=std::max(ans,dif+max[l][r]);69 return;70 }71 int tmp=(a[l]>=a[r])?a[l++]:a[r--];72 dfs(l+1,r,dif+a[l]-tmp);73 dfs(l,r-1,dif+a[r]-tmp);74 }75 int main() {76 getint();77 while(~scanf("%d",&n)) {78 for(register int i=1;i<=n;i++) {79 a[i]=getint();80 }81 init();82 initPart2();83 dfs(1,n,0);84 if(ans!=_inf) {85 printf("%d\n",-ans);86 } else {87 puts("The child will be unhappy...");88 }89 }90 return 0;91 }