自动搬运

查看原文

来自洛谷，原作者为

	zhenjianuo2025 Still we'd fight until our last

搬运于2025-08-24 23:07:13，当前版本为作者最后更新于2024-12-27 09:13:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先有一个基础的 $O(2^n n!)$ 的暴力做法：枚举每一种可能的最终状态，然后进行判定，可以跑过 $n\le 12$。

注意到所有的空隙排成一个二叉树的结构。可以据此设计 DP：$f_{S,U}$ 表示用集合 $S$ 中的结点组成一棵树，在外层强制 $U$ 中的物品不被放入，所形成的空间最长是多少。枚举分裂成的两棵子树 $T_1,T_2$ 进行转移，转移时同时考虑不能被放入的结点集合 $U$ 所造成的长度限制。注意 $S$ 是 $\bar{U}$ 的子集，$T_1$ 是 $S$ 的子集，所以复杂度 $O(4^n)$。注意不要让复杂度带上一个 $n$，实现较为优秀的在卡常后可以无压力地通过。

下面这份代码在 QOJ 跑到了目前的最优解：

#include<bits/stdc++.h>
using namespace std;
#define vec vector
#define siz(vec) ((int)(vec).size())
#define all(vec) (vec).begin(),(vec).end()
template<class T>
void operator +=(vec<T> &a,T b){a.push_back(b);}
#define int long long
#define inf (long long)(1e18)
template<class T>
bool Min(T &x,T y){return x>y?x=y,1:0;}
template<class T>
bool Max(T &x,T y){return x<y?x=y,1:0;}

int n,m,a[16];
int f[1<<14];
int sum[1<<14],rmq[15];
int U;
int dfs(int S){
    if(!S)return rmq[n];
    if(f[S]!=0)return f[S];

    int i=__builtin_ctz(S),SS=S^(1<<i);
    for(int T=SS;;T=(T-1)&SS){
        Max(f[S],dfs(T)+dfs(SS^T)+a[i]);
        if(!T)break;
    }
    
    int x=rmq[i];
    Min(f[S],x);
    if(sum[S]>=x){
        f[S]=-inf;
    }
    return f[S];
}
main(){
    cin>>m>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    vec<int> ans;
    for(int U=0;U<(1<<n);U++){
        rmq[0]=m+1;
        for(int i=0;i<n;i++){
            rmq[i+1]=rmq[i];
            if(~U>>i&1)Min(rmq[i+1],a[i]);
        }
        if(U)sum[U]=sum[U^(U&(-U))]+a[__builtin_ctz(U)];

        memset(f,0,sizeof f);
        if(dfs(U)>m){
            ans+=sum[U];
        }
    }

    sort(all(ans));
    ans.erase(unique(all(ans)),ans.end());
    cout<<siz(ans)<<'\n';
    for(auto x:ans)cout<<x<<' ';
}