关于爆搜

mona @ 2018-10-06 16:53:35

by __Kinger__ @ 2018-10-06 16:57:03

@mona 大佬代码看看

by yybyyb @ 2018-10-06 17:01:24

@mona 神仙

by 星小雨 @ 2018-10-06 17:01:50

@mona 因为这道题正解也不过是折半搜索

by λᴉʍ @ 2018-10-06 17:08:42

@mona 神仙

by mona @ 2018-10-06 17:11:54

@Kinger 加了个信仰剪枝，特殊数据有奇效。主要是开始被误导没想到meet in the middle就打了个这个。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<set>
#include<queue>
#include<map>
#include<vector>
#define N 50
#define ll long long
#define RG register

using namespace std;
inline ll read(){
    RG ll x=0,o=1; RG char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') o=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=((x<<3)+(x<<1))+ch-'0',ch=getchar();
    return x*o;
}

int n; ll m,val[N],sum[N],ans;

inline void Dfs(int k,ll now){
    if(now+sum[k]<=m) { ans+=1LL<<(n-k+1); return ; }
    Dfs(k+1,now); if(now+val[k]<=m) Dfs(k+1,now+val[k]);
}

int main(){
    n=read(),m=read(); for(RG int i=1;i<=n;++i) val[i]=read();
    sort(val+1,val+1+n),reverse(val+1,val+1+n);
    for(RG int i=n;i;--i) sum[i]=sum[i+1]+val[i];
    Dfs(1,0),cout<<ans<<endl;
}

by __Kinger__ @ 2018-10-06 20:29:45

@mona 嗯