题解：P11427 [清华集训 2024] 绝顶之战

zhenjianuo2025 · 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<<' ';
}