应用
起点和终点是已知的，需要确定从起点到终点需要多少步
P4799 [CEOI2015 Day2] 世界冰球锦标赛
此题不需要去重
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll m,a[50],ans;
int p;
ll ans1[1<<21],idx1,ans2[1<<21],idx2;
void dfs1(int k,ll sum)
{
if(sum > m)return;
if(k > p)
{
ans1[++idx1] = sum;
return;
}
dfs1(k+1,sum+a[k]);
dfs1(k+1,sum);
}
void dfs2(int k,ll sum)
{
if(sum > m)return;
if(k > n)
{
ans2[++idx2] = sum;
return;
}
dfs2(k+1,sum+a[k]);
dfs2(k+1,sum);
}
int main()
{
scanf("%d%lld",&n,&m);
for(int i = 1;i<= n;i++)scanf("%lld",a+i);
p = n/2;
dfs1(1,0);
dfs2(p+1,0);
sort(ans1+1,ans1+1+idx1);
sort(ans2+1,ans2+1+idx2);
int p2 = idx2;
for(int i = 1;i <= idx1;i++)
{
while(ans2[p2] + ans1[i] > m)p2--;
ans += p2;
}
printf("%lld",ans);
return 0;
}