我的天,折半搜索(meet in the middle),依稀记得我学过,但是真的不记得。。。。
从状态图上起点和终点同时开始进行宽度/深度优先搜索,如果发现相遇了,那么可以认为是获得了可行解。
这道题,每一个元素会有3种状态,分别是在第一个集合或者第二个集合亦或者不在集合中。如果直接暴力去搜的话,时间复杂度是三次方级别的,不能被接受。
所以考虑折半搜索,就可以直接把复杂度上的指数砍半,就可以过掉这道题了。
折半搜索实现
#include<bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int N=25,M=2e6+100;
int n;
int ans[M];
int a[M];
int s,tot;
vector<int> p[M];
map<int,int> b;
void dfs1(int x,int sum,int now)
{
//对前一半进行搜索,now->对取了的数进行状态压缩
if(x>n/2)
{
if(b[sum]==0) b[sum]=++tot;//李三华
p[b[sum]].pb(now);
return;
}
dfs1(x+1,sum+a[x],now|(1<<(x-1)));
dfs1(x+1,sum-a[x],now|(1<<(x-1)));
dfs1(x+1,sum,now);
//分三种情况讨论,要么在左,要么在右,要么都不在
}
void dfs2(int x,int sum,int now)
{
//对后一半进行搜索
if(x>n)
{
int t=b[sum];
if(t!=0)
for(int i=0;i<p[t].size();i++)
ans[p[t][i]|now]=1;
//对于每一种可能的组合,将值赋为1,
//因为题目中要求的方案数为取数的方案数而不是分数的方案数
//因此不是+1而是=1
return;
}
dfs2(x+1,sum+a[x],now|(1<<(x-1)));
dfs2(x+1,sum-a[x],now|(1<<(x-1)));
dfs2(x+1,sum,now);
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
dfs1(1,0,0),dfs2(n/2+1,0,0);
for(int i=1;i<=(1<<n);i++) s+=ans[i];
cout<<s<<endl;
return 0;
}
//meet in the middle(折半搜索)
也可以用状态压缩实现大部分折半搜索的题目,这道题也可以用三进制状态压缩去做。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int B[2],a[22],pow3[12],ans;
bool st[(1<<20+5)];
map<int,vector<int>> f[2];
signed main()
{
cin>>n;
B[0]=n/2,B[1]=n-B[0];
for(int i=0;i<n;i++) cin>>a[i];
pow3[0]=1;
for(int i=1;i<=B[1];i++) pow3[i]=pow3[i-1]*3;
for(int t=0;t<=1;t++)
for(int s=0;s<pow3[B[t]];s++)
{
int d=0,S=(1<<B[0])-1;
if(t==1) S=((1<<n)-1)-S;
for(int i=0;i<B[t];i++)
{
int v=(s/pow3[i])%3;
if(v==1) d+=a[i+t*B[0]];
else if(v==2) d-=a[i+t*B[0]];
else S-=(1<<(i+t*B[0]));
}
f[t][d].push_back(S);
}
for(auto a:f[0])
for(int b:a.second)
for(int c:f[1][-a.first])
if(!st[c|b]) ans++,st[c|b]=true;
cout<<ans-1<<endl;
return 0;
}
标签:折半,Subsets,int,USACO12OPEN,sum,long,搜索,Balanced,now
From: https://www.cnblogs.com/tangml/p/18415284