目录
显示
题目链接
https://www.luogu.org/problem/P4799
题解
考虑折半搜索来解决问题。
我们将价值数组分成两半,搜索的时候只从其中一半里选择,并记录每次搜索回溯时的花费。
计数的时候,我们针对每个状态,算出能和这个状态搭配的另一半搜索的状态数。
通过将状态数组排序后二分查找,每个状态可以在 \(O(\log n)\) 的时间内算出能与它搭配的状态数。
#include <iostream>
#include <algorithm>
using namespace std;
long long a[45],n,m,resa[1500005],resb[1500005],ans;
void dfs(int l,int r,long long used,long long p[],long long&cnt)
{
if(used>m)return;
if(l>r)
{
p[++cnt]=used;
return;
}
dfs(l+1,r,used+a[l],p,cnt);
dfs(l+1,r,used,p,cnt);
}
int main()
{
cin>>n>>m;
long long mid=n>>1,cnta=0,cntb=0;
for(int i=1;i<=n;i++)
cin>>a[i];
dfs(1,mid,0,resa,cnta);
dfs(mid+1,n,0,resb,cntb);
sort(resa+1,resa+cnta+1);
for(int i=1;i<=cntb;i++)
ans+=upper_bound(resa+1,resa+cnta+1,m-resb[i])-resa-1;
cout<<ans<<endl;
return 0;
}
#include <iostream>
#include <algorithm>
using namespace std;
long long a[45],n,m,resa[1500005],resb[1500005],ans;
void dfs(int l,int r,long long used,long long p[],long long&cnt)
{
if(used>m)return;
if(l>r)
{
p[++cnt]=used;
return;
}
dfs(l+1,r,used+a[l],p,cnt);
dfs(l+1,r,used,p,cnt);
}
int main()
{
cin>>n>>m;
long long mid=n>>1,cnta=0,cntb=0;
for(int i=1;i<=n;i++)
cin>>a[i];
dfs(1,mid,0,resa,cnta);
dfs(mid+1,n,0,resb,cntb);
sort(resa+1,resa+cnta+1);
for(int i=1;i<=cntb;i++)
ans+=upper_bound(resa+1,resa+cnta+1,m-resb[i])-resa-1;
cout<<ans<<endl;
return 0;
}
#include <iostream> #include <algorithm> using namespace std; long long a[45],n,m,resa[1500005],resb[1500005],ans; void dfs(int l,int r,long long used,long long p[],long long&cnt) { if(used>m)return; if(l>r) { p[++cnt]=used; return; } dfs(l+1,r,used+a[l],p,cnt); dfs(l+1,r,used,p,cnt); } int main() { cin>>n>>m; long long mid=n>>1,cnta=0,cntb=0; for(int i=1;i<=n;i++) cin>>a[i]; dfs(1,mid,0,resa,cnta); dfs(mid+1,n,0,resb,cntb); sort(resa+1,resa+cnta+1); for(int i=1;i<=cntb;i++) ans+=upper_bound(resa+1,resa+cnta+1,m-resb[i])-resa-1; cout<<ans<<endl; return 0; }