SP11469 SUBSET-Balanced Cow Subsets meet-in-the-middle+状压

时间：2022-09-06 17:25:49

正解:折半搜索

解题报告:

传送门!

这题我开始看到的时候贼开心地就把这题的代码直接粘过来辣

然后就T辣,,,仔细思考一下,为什么呢?

因为会枚举到很多相同的状态

举个eg

20

1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1

那就考虑怎么改进?

因为想到,它枚举到了很多相同的状态

那我们就可以直接存某个状态能否达成,开个桶记录

然后最后for枚举状态地统计就好了

(然后还有一个就是,记得开int,longlong会超时,不要问我怎么知道的TT

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define rg register

#define ll int

#define rp(i,x,y) for(rg ll i=x;i<=y;++i)

const ll N=+,M=+;

ll n,m,a[N],cnt,as;

bool vis[M];

map<ll,ll>mp;

vector<ll>dist[M<<];

il ll read()

{

    rg char ch=getchar();rg ll x=;rg bool y=;

    while(ch!='-' && (ch>'' || ch<''))ch=getchar();

    if(ch=='-')ch=getchar(),y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=getchar();

    return y?x:-x;

}

void dfs1(ll num,ll tot,ll stat)

{

    if(num>m){if(mp.find(tot)==mp.end())mp[tot]=++cnt;dist[mp[tot]].push_back(stat);return;}

    dfs1(num+,tot,stat);

    dfs1(num+,tot+a[num],stat|(<<(num-)));

    dfs1(num+,tot-a[num],stat|(<<(num-)));

}

void dfs2(ll num,ll tot,ll stat)

{

    if(num>n)

    {if(mp.find(tot)==mp.end())return;ll id=mp[tot],sz=dist[id].size();rp(i,,sz-)vis[dist[id][i]|stat]=;return;}

    dfs2(num+,tot,stat);

    dfs2(num+,tot+a[num],stat|(<<(num-)));

    dfs2(num+,tot-a[num],stat|(<<(num-)));

}

int main()

{

    n=read();m=n>>;rp(i,,n)cin>>a[i];

    dfs1(,,);dfs2(m+,,);rp(i,,(<<n))as+=vis[i];printf("%d\n",as);return ;

}

相关文章