[清华集训 2024] 绝顶之战

比较牛的一个题目。

考虑如果在某一个位置放置了一个物品，那么剩余的空间就会变成 $2$ 个没有关系的单独区间。

注意到 $n\le 14$，那么我们显然可以枚举一个子集 $S$，然后判断是否有一种方案可以把 $S$ 中的元素恰好放进去。

有一个性质，如果 $S$ 确定了，那么在 $[\sum\limits_{i\in S} a_i,+\infty)$ 是具有单调性的，即如果 $x$ 可以做到那么这个区间内比 $x$ 小的是都可以做到的。

上面性质的证明是容易的，我们只需要缩小之间的间距就可以了。

考虑设 $f_{i,S,T}$ 表示考虑了 $[i,n]$ 区间内的数，$T$ 里面的数不被选择，现在这一段内选择了 $S$ 的最长距离。

于是我们只需要判断是否有 $f_{1,S,[n]/S}\ge m$ 且 $\sum\limits_{i\in S} a_i\le m$ 就可以了。

考虑怎么转移，我们分情况讨论：

如果 $i\in S$，那么有转移：

$$f_{i,S,T}\gets a_i+\max\limits_{S'\subseteq S} \{f_{S',T}+f_{S/S',T}\}$$
如果 $i\in T$，那么有转移：

$$f_{i,S,T}\gets \min(a_{i}-\varepsilon,f_{S,T/i})$$

这里之所以取 $\min$ 是因为我们是从后向前转移的，如果这个位置 $i$ 可以放进去，那么就 $i$ 就肯定会放进去。

于是做完了，考虑分析时间复杂度。

因为 $S\cap T=\varnothing$，所以说一个物品在状态中会有 $3$ 中情况，分别是属于 $S$、属于 $T$ 还有都不属于，于是状态的数量就是 $O(3^n)$ 的。

然而枚举了 $S'$ 于是就相当于添加了一种状态，所以最后的复杂度就是 $O(4^n)$，可以通过。

```cpp
#include<iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>
#define int long long
using namespace std;
const int N=14,inf=1e18,mod=998244353;
int m,n,a[N],ss[1<<N];
unordered_map<int,int> f[N][1<<N];
vector<int> ans;
int dfs(int i,int S,int T){
    if(i==n){
		return inf;
	}
    if((T&(1<<i))&&a[i]<=ss[S]){
		return -inf;
	}
    if(f[i][S].find(T)!=f[i][S].end()){
		return f[i][S][T];
	}
    if(T&(1<<i)){
		return f[i][S][T]=min(a[i],dfs(i+1,S,T^(1<<i)));
	}
    if(S&(1<<i)){
        int A=S^(1<<i),V=-inf;
        for(int s=A;;s=(s-1)&A){
            V=max(V,dfs(i+1,s,T)+dfs(i+1,A^s,T));
            if(!s) break;
        }
        return f[i][S][T]=a[i]+V;
    }
    return f[i][S][T]=dfs(i+1,S,T);
}
signed main(){
    ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>m>>n;
    for(int i=0;i<n;i++){
		cin>>a[i];
	}
    for(int S=1;S<(1<<n);S++){
		ss[S]=ss[S^(S&(-S))]+a[__lg(S&(-S))];
	}
    for(int S=0;S<(1<<n);S++){
		if(ss[S]<=m&&m<dfs(0,S,(1<<n)-1-S)){
			ans.push_back(ss[S]);
		}
	}
    sort(ans.begin(),ans.end());
	ans.erase(unique(ans.begin(),ans.end()),ans.end());
    cout<<ans.size()<<'\n';
	for(int i:ans){
		cout<<i<<' ';
	}
	return 0;
}
```

正在渲染内容...