题目大意：
有一个长度为n的数列，A和B两个人轮流从两端取数，B先取，A想使分数严格小于B且尽量接近B，问两人分数之差最小是多少。
思路：
折半搜索，先预处理出长度为part的最大差最小差，再预处理出后面一段能取到的不同差值，然后dfs，当范围等于part时，就在数组中二分查找一下。
1 #include<cstdio> 2 #include<cctype> 3 #include<vector> 4 #include<ext/hash_set> 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<int> v[N]; 37 __gnu_cxx::hash_set<int> 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<<part;j++) { 44 int tmp=0,l=i,r=i+part*2-1; 45 for(int k=0;k<part;k++) { 46 tmp-=(a[l]>=a[r])?a[l++]:a[r--]; 47 tmp+=(!(j&(1<<k)))?a[l++]:a[r--]; 48 } 49 if(s.find(tmp)==s.end()) { 50 s.insert(tmp); 51 v[i].push_back(tmp); 52 } 53 } 54 std::sort(v[i].begin(),v[i].end()); 55 } 56 } 57 void dfs(int l,int r,int dif) { 58 if(r-l+1==part*2) { 59 std::vector<int>::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 ",-ans); 86 } else { 87 puts("The child will be unhappy..."); 88 } 89 } 90 return 0; 91 }
这段代码在SimpleOJ上交比暴力还慢。