自动搬运

查看原文

来自洛谷，原作者为

	defense 这个家伙很菜，什么也没有留下

搬运于2025-08-24 21:33:46，当前版本为作者最后更新于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;//功德圆满
}

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