atcoder abc 184 F - Programming Contest

meet-in-the-middle 基础算法（优化dfs）
meet−in−the−middle（又称折半搜索、双向搜索）对于n<=40的搜索类型题目，一般都可以采用该算法进行优化，很稳很暴力。
我们可以将n分成2部分这样可以将 -> 对于n=40的可以将复杂度降到n*logn左右 n->2^20;
然后我们通过dfs将前半段和后半段的所有不大于T的数存起来，在枚举一个的时候，判断另一个。

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

typedef long long ll;
typedef double dl;

const int N = 1<<20;
const int M = 1e9+7;
const int INF = 0x7fffffff;

int n,m,T;
int a[N];
int b[N];
int c[N];

void dfs(int l,int r,int v,int d[],int &num)
{
    if(v>T) return ;
    if(l==r)
    {
        d[++num]=v;
        return ;
    }
    dfs(l+1,r,v+a[l],d,num);
    dfs(l+1,r,v,d,num);
}

void solve()
{
    scanf("%d%d",&n,&T);
    for(int i=1;i<=n;i++)    scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    int len=n/2+1;
    int b_num=0;
    dfs(1,len,0,b,b_num);
    sort(b+1,b+b_num+1);
    int c_num=0;
    dfs(len,n+1,0,c,c_num);
    sort(c+1,c+c_num+1);
    int ptr=c_num;
    int maxn=0; 
    for(int i=1;i<=b_num;i++)
    {
        while(b[i]+c[ptr]>T) ptr--;
        maxn=max(maxn,b[i]+c[ptr]);
    }
    printf("%d",maxn);
}

int main()
{
    solve();
}