AtCoder Regular Contest 100 E-Or Plus Max

Description

There is an integer sequence of length \(2^N\): \(A_0, A_1, ..., A_{2^N-1}\). (Note that the sequence is 0-indexed.)

For every integer K satisfying \(1 \leq K \leq 2^N-1\), solve the following problem:

• Let iand j be integers. Find the maximum value of \(A_i + A_j\) where \(0 \leq i < j \leq 2^N-1\) and \((i \or j) <= K\) Here, or denotes the bitwise OR.

Limit

\(1 <= n <= 18\)

\(1 <= A_i <= 1e9\)

All values in input are integers.

Example

input1

2
1 2 3 1

output1

3
4
5

input2

3
10 71 84 33 6 47 23 25

output2

81
94
155
155
155
155
155

input3

4
75 26 45 72 81 47 97 97 2 2 25 82 84 17 56 32

output3

101
120
147
156
156
178
194
194
194
194
194
194
194
194
194

solution

用 pair<int,int> Max[state] 表示i or j = state 时的最大值和次大值为多少（没有次大，次大为-1）

答案随着state的增大单调递增

当求解 Max[state] 时，可以枚举state的子集，然后选出其中的最大的和次大的。同时由于上面的那条性质，所以子集大的答案一定更优，那么就不必枚举state的所有子集，只需要比较它的前n大的子集即可，也就是将state的每一个二进制1尝试取反变成0之后的那最多n个。

#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int A[1 << 18];
pair<int,int> Max[1 << 18];

inline bool cmp(const int &x , const int &y) { return A[x] > A[y]; }

int main()
{
	int n , Ans = 0;
	cin >> n;
	for(int i = 0 ; i < (1 << n) ; ++i)
		cin >> A[i];
	for(int i = 0 ; i < (1 << n) ; ++i)
	{
		vector<int> v; v.push_back(i);
		for(int j = 0 ; j < n ; ++j)
			if(i & (1 << j))
			{
				v.push_back(Max[i ^ (1 << j)].first);
				if(Max[i ^ (1 << j)].second != -1)
					v.push_back(Max[i ^ (1 << j)].second);
			}
		sort(v.begin() , v.end() , cmp);
		v.erase(unique(v.begin() , v.end()) , v.end());
		if(v.size() == 1) 
			Max[i] = make_pair(v[0] , -1);
		else
			Max[i] = make_pair(v[0] , v[1]);
		Ans = max(Ans , A[Max[i].first] + (~Max[i].second ? A[Max[i].second] : 0));
		if(i) cout << Ans << '\n';
	}
	return 0;
}