AT_abc184_f [ABC184F] Programming Contest 题解

题目传送门

前置知识

Meet in the middle

解法

• 非正解
  • 当成超大背包来做，暴力枚举每个数是否进行相加。
  • 时间复杂度为 \(O(2^{n})\)。

  ll p[50],ans=0;
  void dfs(ll x,ll n,ll m,ll worth)
  {
  	if(x==n+1)
  	{
  		if(worth<=m)
  		{
  			ans=max(ans,worth);
  		}
  	}
  	else
  	{
  		if(worth+p[x]<=m)
  		{
  			dfs(x+1,n,m,worth+p[x],worth+p[x]);
  		}
  		dfs(x+1,n,m,worth);
  	}
  }
  int main()
  {
  	ll n,m,i;
  	cin>>n>>m;
  	for(i=1;i<=n;i++)
  	{
  		cin>>p[i];
  	}
  	dfs(1,n,m,0);
  	cout<<ans<<endl;
  	return 0;
  }
  

• 正解
  • 考虑优化搜索过程，使用双向搜索。具体地，对于 \(1 \sim \left\lfloor \frac{n}{2}\right\rfloor\) 进行第一遍搜索，对于得到的价值存到一个 set 里面。对于 \(\left\lfloor \frac{n}{2}\right\rfloor+1 \sim n\) 进行第二遍搜索，对于得到的总和在 set 里面找到满足 \(\le T\) 减去当前总和的最大总和，进行转移即可。
  • 时间复杂度为 \(O(2^{\frac{n}{2}}n)\) 。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ull unsigned long long
#define sort stable_sort 
#define endl '\n'
set<ll>vis;
ll p[50],ans=0;
void dfsl(ll x,ll n,ll m,ll worth)
{
    if(x==n+1)
    {
        if(worth<=m)
        {
            vis.insert(worth);
        }
    }
    else
    {
        if(worth+p[x]<=m)
        {
            dfsl(x+1,n,m,worth+p[x]);
        }
        dfsl(x+1,n,m,worth);
    }
}
void dfsr(ll x,ll n,ll m,ll worth)
{
    if(x==n+1)
    {
        if(worth<=m)
        {
            ans=max(ans,worth+(*(--vis.upper_bound(m-worth))));
        }
    }
    else
    {
        if(worth+p[x]<=m)
        {
            dfsr(x+1,n,m,worth+p[x]);
        }
        dfsr(x+1,n,m,worth);
    }
}
int main()
{
    ll n,m,i;
    cin>>n>>m;
    for(i=1;i<=n;i++)
    {
        cin>>p[i];
    }
    dfsl(1,n/2,m,0);
    dfsr(n/2+1,n,m,0);
    cout<<ans<<endl;
    return 0;
}