不难发现我们可以处理出每个状态所有子集中 \(a_i\) 的最大值和次大值，用一个 pair<int,int> 维护，跑一遍 \(\text{SOSDP}\)，这时每个状态的权值就是最大值加次大值，最终输出的每一个答案都是一个前缀最大值。
点击查看代码
#include <bits/stdc++.h>
#define FL(i, a, b) for(int i = a; i <= b; i++)
#define FR(i, a, b) for(int i = a; i >= b; i--)
using namespace std;
int n, U, ans;
pair<int, int> f[1 << 18];
void upd(pair<int, int> &a, int x){
if(x > a.first) a.second = a.first, a.first = x;
else if(x > a.second) a.second = x;
}
int main(){
scanf("%d", &n), U = (1 << n) - 1;
FL(s, 0, U) scanf("%d", &f[s].first);
FL(i, 1, n) FR(s, U, 1) if(s & (1 << i - 1))
upd(f[s], f[s ^ (1 << i - 1)].first), upd(f[s], f[s ^ (1 << i - 1)].second);
FL(s, 1, U) ans = max(ans, f[s].first + f[s].second), printf("%d\n", ans);
return 0;
}