codeforces/gym/101291/B

时间:2023-03-09 18:08:10
codeforces/gym/101291/B

题意:给你n个杠铃的杆子,在给你m个杠铃片,问你能组成多少个重量不同的完整杠铃(杠铃杆子也算一个完整的的杠铃)

解题思路:dfs直接搜,数据很小,每个杠铃片有三种状态(放杆子左边,放杆子右边,两边都不放),用set存一下,去下重,正好要从小到大序输出

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#define ll long long
using namespace std;
int a[20];
int b[20];
int n,m;
int cnt=0;
set<ll>q;
void dfs(ll x,ll l,ll r)
{
if(x>m)
return;
if(l==r)
{
q.insert(r+l);
}
dfs(x+1,l+a[x+1],r);
dfs(x+1,l,r+a[x+1]);
dfs(x+1,l,r);
}
int main()
{
set<ll>ans;
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>b[i];
for(int i=1;i<=m;i++)
cin>>a[i];
a[0]=0;
dfs(0,0,0);
for(int i=1;i<=n;i++)
{
for(set<ll>::iterator it=q.begin();it!=q.end();it++)
{
ans.insert(*it+b[i]);
}
}
for(set<ll>::iterator it=ans.begin();it!=ans.end();it++)
{
cout<<*it<<endl;
}
return 0;
}