题解 P2080 【增进感情】

defense · 2019-05-02 14:29:11 · 题解

说好数据弱的呢？！QWQ

这道题是一道暴搜题。但如果不剪枝，只能拿20分（被“数据比较弱”欺骗）

• 主要思路:记录每一次做掉事情，加上去！
• 剪枝1：当Minn已经最小的时候，就不需要再搜索了，即 abs(xiaoming,xiaohong)=0(如果这个不知道建议初中重读)
• 剪枝2：应为我的题解用了一个数组记录选与不选，随意改选的在前面已经选过了，不需要循环再跑一遍，所以可用一个变量记录上次搜索到的位置，这样就可以避免重复。

  管理员大大最帅了！！！！

  看我讲那么详细，让我过呗！

  code：

  #include<cstdio>
  #include<iostream>
  #include<cmath>
  using namespace std;
  int m,v,a[30],b[30],minn=100000,ga,gb;//m,v，a,b如题意，minn纪录最小值，ga,gb分别记录两人的好感
  bool used[30];//判断是否做过这件事
  void dfs(int deep){//deep记录上次搜索的位置
  if(ga+gb>v){//如果可以在一起
      minn=min(abs(ga-gb),minn);//更新值
  }
  if(minn==0){//最小极值
      return;
  }
  for(int i=deep;i<m;i++){//开始搜索！
      if(used[i]==0){//没做过
          used[i]=1;//设为做过
          ga+=a[i];//加！！
          gb+=b[i];
          dfs(i+1);//继续搜！！！
          ga-=a[i];//减！！
          gb-=b[i];
          used[i]=0;//回溯
      }
  }
  }
  int main(){
  scanf("%d%d",&m,&v);
  for(int i=0;i<m;i++){
      scanf("%d%d",&a[i],&b[i]);
  }
  dfs(0);
  if(minn==100000){//永远无法在一起（出题人太狠毒了）
      printf("-1");
      return 0;
  }
  printf("%d",minn);
  return 0;//功德圆满
  }

  管理员大大最帅了！！！！