D - happy happy happy HDU - 6196（剪枝+中途相遇+搜索）-白红宇

D - happy happy happy HDU - 6196（剪枝+中途相遇+搜索）

阅读量：4114 次

发布时间：2019-05-25

本文共 1810 字，大约阅读时间需要 6 分钟。

(比赛网址）

（题目网址）

题意：Bob正在和一个孩子一起玩耍，一排有n个数字，每个人每次只能从最左边或者shi最右边开始拿一个数，Bob知道孩子每次都会拿左右两边比较大的一个，如果两个数字一样大，Bob会优先拿左边的，现在Bob想让孩子拿的数字之和比自己的大并且自己与孩子的差值尽量小，输出两个人的最小差值，如果不管怎么拿孩子拿的数字都比Bob的小输出“The child will be unhappy...”

思路：这个题中n最大是90，我们可以暴力找答案，普通的没有优化的搜索肯定是会超时的。加上剪枝，中途相遇等方法来优化我们的程序。

剪枝：我们定义两个数组 mi[l][r]:Bob拿的数字与孩子拿的数字之和最小的差值（Bob拿的数字之和-孩子拿的数字之和）

ma[l][r]：Bob拿的数字之和与孩子拿的数字之和最大的差值（Bob拿的数字之和-孩子拿的数字之和）

在dfs（int l,int r,int cha）代表当前要拿的区间是l~r，差值是cha（Bob的数字之和减去孩子的数字之和）

当cha+mi[l][r]>=0时，剪枝，如果当前的差值加上区间l~r最小差值都大于0，肯定找不到答案

当cha+ma[l][r]<=ans,剪枝，ans代表我们当前搜到的最优解，如果当前的差值加上区间l~r的最大差值还小于最优解，在搜肯定找不到比当前答案更优的情况，剪枝。

如果cha+ma[l][r]<0&&cha+ma[l][r]>ans，这时我们更新最优值。
ma[l][r],mi[l][r]的值我们要预先处理，区间在进行初始化的时候要注意，不是所有区间都要初始化，

中途相遇：我们预先处理每个区间内所有差值的情况，当搜到l~r区间，我们可以直接查找与-cha最相近的值。这样也会很省时间。

在预先处理区间内所有答案的方法很巧妙，用二进制枚举的方法找出所有情况，区间的长度选取要注意，区间选择的不合适也会造成超时。

之后再搜索的时候我们直接查找就可以了

it=lower_bound(v[l].begin(),v[l].end(),-cha);

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           using namespace std;const int maxn=90+10;vector
           
             v[maxn];int dis;map
            
              mat;const int inf=0x3f3f3f3f;vector
             
               ::iterator it;int mi[maxn][maxn];int ma[maxn][maxn];int n;int a[maxn];int ans;void Init(){ /// for(int i=0; i
              
               =0; i--) { for(int j=i; j
               
                =a[r]) sub=a[l++]; else sub=a[r--]; mi[i][j]=min(mi[i][j],mi[l+1][r]+a[l]-sub);///选左边 mi[i][j]=min(mi[i][j],mi[l][r-1]+a[r]-sub);///选右边 ma[i][j]=max(ma[i][j],ma[l+1][r]+a[l]-sub);///选左边 ma[i][j]=max(ma[i][j],ma[l][r-1]+a[r]-sub);///选右边 } }}void dfs(int l,int r,int cha){ if(l>r) { if(cha<0) { ans=max(ans,cha); } } /// 剪枝 if(cha+mi[l][r]>=0) return ; if(cha+ma[l][r]
                
                 =a[r]) sub=a[l++]; else sub=a[r--]; dfs(l+1,r,cha-sub+a[l]); dfs(l,r-1,cha-sub+a[r]);}int main(){ while(~scanf("%d",&n)) { for(int i=0; i
                 
                  =a[r]) sum-=a[l++]; else sum-=a[r--]; if(!(s&(1<