原题链接

题解

看到数据范围，想到二进制表示所有已经上去的人的集合的最小乘坐次数，做法为遍历所有子集再遍历所有子集 时间复杂度 \(\sum_{k=0}^n C_n^k 2^k =\ O(3^n)\)

太高了

考虑优化，对于同一个集合、同样最小乘坐次数，总有电梯有空位，而空位越大的乘坐配置越优

依照这个性质，我们在记录某个子集的最小乘坐次数时，再记录其最大的空位

这样一来，我么就不需要对子集的子集进行遍历，只需要对子集的某个人进行遍历

因为对于任意一个子集，总有一个人是最后一个走进电梯里的

而要使子集最优，一定是这个人走进去之前的子集的乘坐次数最小的同时空位最小

code

#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll inf=1e18;

void solve()
{
    ll n,W;
    cin>>n>>W;
    vector<ll> a(n);
    for(ll i=0;i<n;i++) cin>>a[i];

    vector<pair<ll,ll> > dp((1<<n)+10);
    dp[0]={1,0};//载零个人上去，需要一部电梯，载了最少重量的电梯载了0
    for(ll i=1;i<=(1<<n)-1;i++)
    {
        ll tem=i;

        ll t=2e9,w=W;
        while(tem)
        {
            ll now=log2(lowbit(tem));
            tem-=lowbit(tem);
            auto [ti,we]=dp[(1<<now)^i];
            if(ti>t) continue;
            if(we+a[now]<=W)
            {
                if(ti<t)
                {
                    t=ti;
                    w=we+a[now];
                }
                else w=min(we+a[now],w);
            }
            else
            {
                if(ti+1<t)
                {
                    t=ti+1;
                    w=min(a[now],we);
                }
                else w=min(w,min(a[now],we));
            }
        }

        dp[i]={t,w};
    }

    cout<<dp[(1<<n)-1].first;
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll TT=1;
    while(TT--) solve();
    return 0;
}