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

· · 题解

我们注意到一个题目是非多项式复杂度是这个题目 ini 不会的充分条件 /kk。

首先一个观察是，如果我选择集合 S 时 S 占领的最大长度为 f_S，那么 S 可以占领的长度在 [\sum_{i\in S}a_i,x] 这个范围内，非常显然，我们可以缩短两块之间的距离来让总长度变小。

所以我们对于一个集合能否被放进去，我们只需要知道放进去这个集合能占据的最大长度 f_S，如果 f_S\ge m,\sum_{i\in S}a_i\le m，那么 S 是合法的，然后我 DP 求出来 f_S 问题就解决了。

然后你可能会设计一个状态是我考虑 [i,n] 的元素，这个时候我需要选择 S 集合，不选择 [i,n]/S，我最长能占领的长度。

这个状态设计问题在于，假如我当前 i\in S，我需要通过放入 a_i 来把区域划分成两个部分，对于左边的部分，右边的元素也可能可以放到左边，然而我们给左边划分一个 S_1，右边划分一个 S_2，左边会认为 S_2 是他不能放进去的，你就寄了。

所以你发现能放进去的集合和不能放进去的集合的交集并非全集，你的状态就是 f_{i,S,T} 表示我需要放入 S，不能放入 T 的最长长度。

转移的时候考虑如果 i\in S，那么

f_{i,S,T}=a_i+\max_{\{i\}\subseteq S_1\subseteq S}(f_{i+1,S_1/\{i\},T}+f_{i+1,S/S_1,T})

如果 i\in T，那么

f_{i,S,T}=\min(a_i-\varepsilon,f_{i+1,S,T/\{i\}})

如果 i\not\in S 且 i\not \in T，那么

f_{i,S,T}=f_{i+1,S,T}

状态数是 O(3^n) 的，转移是 O(4^n) 的，记忆化一下，常数比较小，可以通过此题。

然后你怎么处理这里的 \varepsilon，你可以对每个状态记录一个其后面是否有一个 -\varepsilon，然后相等的时候特殊处理，不过你会发现，你 DP 出来最后所有的结果都包含一个 \varepsilon，那么你就需要 f_S>m 而非 f_S\ge m。

#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define chkmax(a,b) a=max(a,b)
using namespace std;
mt19937_64 rnd(time(0));
inline char gc() {
    constexpr int S=1<<23;
    static char buf[S],*p1=buf,*p2=buf;
    return (p1==p2&&(p2=(p1=buf)+fread(buf,1,S,stdin),p1==p2)?EOF:*p1++);
}
inline int read() {
    int a=0,b=0;char c=gc();
    while(c<'0'||c>'9')b^=(c=='-'),c=gc();
    while(c>='0'&&c<='9')a=a*10-48+c,c=gc();
    return b?-a:a;
}
const int N=14,inf=1e18+7;
int n,m,s;
int a[N];
int sum[1<<N];
vector<int> ans;
unordered_map<int,int> f[N][1<<N];
int dp(int p,int S,int T){
    if(p==n)return inf;
    if((T>>p&1)&&(a[p]<=sum[S]))return -inf;
    if(f[p][S].find(T)!=f[p][S].end())return f[p][S][T];
    int res=0;
    if(S>>p&1){
        int nS=S^(1<<p),res=-inf;
        for(int S1=nS;S1;S1=(S1-1)&nS)chkmax(res,a[p]+dp(p+1,S1,T)+dp(p+1,S1^nS,T));
        chkmax(res,a[p]+dp(p+1,0,T)+dp(p+1,nS,T));
        return f[p][S][T]=res;
    }
    if(T>>p&1)return f[p][S][T]=min(a[p],dp(p+1,S,T^(1<<p)));
    return f[p][S][T]=dp(p+1,S,T);
}
signed main(){
    m=read(),n=read(),s=1<<n;
    for(int i=0;i<n;i++)a[i]=read();
    for(int i=0;i<s;i++)for(int j=0;j<n;j++)if(i>>j&1)sum[i]+=a[j];
    for(int i=0;i<s;i++)if(sum[i]<=m&&m<=dp(0,i,(s-1)^i))ans.pb(sum[i]);
    sort(ans.begin(),ans.end()); ans.erase(unique(ans.begin(),ans.end()),ans.end());
    printf("%d\n",(int)ans.size());
    for(int v:ans)printf("%lld ",v);
    return 0;
}
//  Think twice,code once