洛谷 2036. 双DFS就可以爆搜两种选择的题目
原题链接
简单
作者:
君故
,
2023-03-28 11:33:18
,
所有人可见
,
阅读 127
#include<bits/stdc++.h>
using namespace std;
const int N=20;
int s[N],b[N];
int n;
bool sts[N],stb[N];
int res=0x7f; //可以在全局变量里进行初始化,不写const即可
void dfs(int sums,int sumb)
{
if(sums!=0&&sumb!=0&&sums!=sumb)
res=min(res,abs(sums-sumb));
for(int i=1;i<=n;i++)
{
if(!sts[i])
{
sts[i]=true;
if(sums==0) dfs(sums+s[i],sumb);
else dfs(sums*s[i],sumb);
sts[i]=false;
}
}
for(int i=1;i<=n;i++)
{
if(!stb[i])
{
stb[i]=true;
dfs(sums,sumb+b[i]);
stb[i]=false;
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>s[i]>>b[i];
dfs(0,0);
cout<<res;
}