原题链接

折半搜索:一个我做一道相关题能T10次的算法

参考了大佬的题解,本蒟蒻没想出来怎么去重(搜索也没想到...绕在只放第x组的死循环里),但是大佬的题解也是T了第5点,开了O₂才过...

思路:

       首先明确重复的方法与所取砝码的质量无关,只与取的分别是谁有关.也就是说 测试数据 4 3 3 3 3 只有7种方法

       分别是[1,2] [3,4],[1,2,3,4],[1,3],[1,4],[2,3],[2,4].根据我们枚举的合法方案,可以猜想用二进制记录所选的砝码.只要前半和后半搜索和为0就记录前半和后半所选砝码.根据所选砝码的合法性再一个个加.

 1 #include <iostream> 
 2 #include <cstring>
 3 #include <unordered_map>
 4 #include <vector>
 5 #include <algorithm>
 6 #include <set>
 7 using namespace std;
 8 typedef long long LL;
 9 const int N = 25,M = (1<<21),S = (1<<11);
10 int a[N],n,idx;
11 bool vis[M];
12 unordered_map<LL,int> mp;
13 vector<int> L[M];
14 void dfs(int l,int r,LL sum,int now)
15 {
16     if(l>r)
17     {
18         if(!mp.count(sum)) mp[sum] = ++idx;
19         L[mp[sum]].push_back(now);//当前和能被哪些砝码凑出 
20         return;
21     }
22     dfs(l+1,r,sum,now);
23     dfs(l+1,r,sum+a[l],now|(1<<(l-1)));
24     dfs(l+1,r,sum-a[l],now|(1<<(l-1)));
25 }
26 void dfs_2(int l,int r,LL sum,int now)
27 {
28     if(l>r)
29     {
30         if(mp.count(sum))
31         {
32             int m = mp[sum];
33             for(int i=0;i<L[m].size();i++)
34               vis[L[m][i]|now] = 1;
35         }
36         return;
37     }
38     dfs_2(l+1,r,sum,now);
39     dfs_2(l+1,r,sum+a[l],now|(1<<l-1));
40     dfs_2(l+1,r,sum-a[l],now|(1<<l-1));
41 }
42 int main()
43 {
44     scanf("%d",&n);
45     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
46     dfs(1,n/2+1,0,0);
47     dfs_2(n/2+2,n,0,0);
48     LL ans = 0;
49     for(int i=1;i<1<<n;i++)
50       ans+=vis[i];
51     printf("%lld\n",ans);
52     return 0;
53 }