题目大意：
有一个长度为n的数列，A和B两个人轮流从两端取数，B先取，A想使分数严格小于B且尽量接近B，问两人分数之差最小是多少。
思路：
折半搜索，先预处理出长度为part的最大差最小差，再预处理出后面一段能取到的不同差值，然后dfs，当范围等于part时，就在数组中二分查找一下。
#include<cstdio>
#include<cctype>
#include<vector>
#include<ext/hash_set>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'';
while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');
return x;
}
const int inf=0x7fffffff,_inf=-0x80000000;
const int N=;
int a[N];
int max[N][N],min[N][N],ans,n,part;
inline void init() {
ans=_inf;
for(register int i=;i<=n;i++) {
for(register int j=;j<=n;j++) {
max[i][j]=_inf;
min[i][j]=inf;
}
}
for(register int i=;i<=n;i++) {
max[i][i-]=min[i][i-]=;
}
for(register int i=n;i;i--) {
for(register int j=i;j<=n;j++) {
int l=i,r=j;
int tmp=(a[l]>=a[r])?a[l++]:a[r--];
max[i][j]=std::max(a[l]+max[l+][r],a[r]+max[l][r-])-tmp;
min[i][j]=std::min(a[l]+min[l+][r],a[r]+min[l][r-])-tmp;
}
}
}
std::vector<int> v[N];
__gnu_cxx::hash_set<int> s;
void initPart2() {
part=std::min(,n/);
for(int i=;i<=n+-part*;i++) {
s.clear();
v[i].clear();
for(int j=;j<<<part;j++) {
int tmp=,l=i,r=i+part*-;
for(int k=;k<part;k++) {
tmp-=(a[l]>=a[r])?a[l++]:a[r--];
tmp+=(!(j&(<<k)))?a[l++]:a[r--];
}
if(s.find(tmp)==s.end()) {
s.insert(tmp);
v[i].push_back(tmp);
}
}
std::sort(v[i].begin(),v[i].end());
}
}
void dfs(int l,int r,int dif) {
if(r-l+==part*) {
std::vector<int>::iterator it=std::lower_bound(v[l].begin(),v[l].end(),-dif);
if(it==v[l].begin()&&*it==-dif) return;
if(it==v[l].end()||*it==-dif) it--;
if(dif+*it<) ans=std::max(ans,dif+*it);
return;
}
if(dif+min[l][r]>=) return;
if(dif+max[l][r]<=ans) return;
if(dif+max[l][r]<) {
ans=std::max(ans,dif+max[l][r]);
return;
}
int tmp=(a[l]>=a[r])?a[l++]:a[r--];
dfs(l+,r,dif+a[l]-tmp);
dfs(l,r-,dif+a[r]-tmp);
}
int main() {
getint();
while(~scanf("%d",&n)) {
for(register int i=;i<=n;i++) {
a[i]=getint();
}
init();
initPart2();
dfs(,n,);
if(ans!=_inf) {
printf("%d\n",-ans);
} else {
puts("The child will be unhappy...");
}
}
return ;
}
这段代码在SimpleOJ上交比暴力还慢。