原题链接

考察:双向dfs

思路:

       爆搜的时间复杂度是O(2⁴⁰).明显TLE.背包的时间复杂度是O(m*n) 也会TLE.所以需要优化.

       这里的优化考虑折半搜索.也就只搜索一半.在搜索另一半的时候进行答案累加.这里先预处理在0~n/2的比赛里选的方案.然后在搜另一半的时候二分找到最大的与当前花费和<=m的左半边下标.这样就优化查找.具体还是看代码吧...

      本蒟蒻自己写的代码T了...O₂能过,但还是参考题解不开O₂.题解是预处理了两边的方案再累加.

 1 #include <iostream> 
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <vector>
 5 using namespace std;
 6 typedef long long LL;
 7 typedef pair<LL,int> PIL;
 8 const int N = 45,M = 1<<23;
 9 LL c[N],m,ans,L[M],R[M];
10 int n,sz;
11 void dfs(int st,LL cost,LL a[],int ed,int& cnt)
12 {
13     if(st>ed)
14     {
15         a[cnt++] = cost;
16         return;
17     }
18     if(c[st]<=m-cost) dfs(st+1,cost+c[st],a,ed,cnt);
19     dfs(st+1,cost,a,ed,cnt);
20 }
21 int main()
22 {
23     scanf("%d%lld",&n,&m);
24     for(int i=0;i<n;i++) scanf("%lld",&c[i]);
25     sort(c,c+n);
26     reverse(c,c+n);
27     int cnt = 0;
28     dfs(0,0,L,n/2,sz);
29     dfs(n/2+1,0,R,n-1,cnt);
30     sort(L,L+sz);
31     for(int i=0;i<cnt;i++)
32     {
33         LL idx = upper_bound(L,L+sz,m-R[i])-L;
34         ans+=idx;
35     }
36     printf("%lld\n",ans);
37     return 0;
38 }

 

 1 #include <iostream> 
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 typedef long long LL;
 6 typedef pair<LL,int> PIL;
 7 const int N = 45,M = 1<<22;
 8 LL c[N],m,ans;
 9 int n,sz;
10 PIL l[M];
11 void dfs_1(int st,int now,LL cost)
12 {
13     l[sz++] = {cost,now};
14     if(cost+c[n/2]>m) return;
15     if(st>n/2) return;
16     if(!(now>>st&1)&&c[st]<=m-cost) dfs_1(st+1,now|(1<<st),cost+c[st]);
17     dfs_1(st+1,now,cost);
18 }
19 void dfs_2(int st,int now,LL cost)
20 {
21     int low = 0,high = sz-1;
22     while(low<high)
23     {
24         int mid = low+high+1>>1;
25         if(l[mid].first<=m-cost) low = mid;
26         else high = mid-1;
27     }
28     if(high>=0) ans+=high+1;
29     for(int i=st;i<n;i++)
30        if(!(now>>st&1)&&c[i]<=m-cost) dfs_2(i+1,now|(1<<i),cost+c[i]);
31 }
32 int main()
33 {
34     scanf("%d%lld",&n,&m);
35     for(int i=0;i<n;i++) scanf("%lld",&c[i]);
36     sort(c,c+n);
37     reverse(c,c+n);
38     dfs_1(0,0,0);
39     sort(l,l+sz);
40     sz = unique(l,l+sz)-l;
41     dfs_2(n/2+1,0,0);
42     printf("%lld\n",ans);
43     return 0;
44 }

吸氧才过的代码