题意

给定整数序列 $A$ ，要构造一个数列 $B$ ，其中 $B$ 由 $0, 1$ 组成，且 $0$ 的个数等于 $1$ 的个数。

在此前提下，构造一个数列 $B$ 使得 $\sum_{i=2}^n A_i*(B_i \otimes B_{\left\lfloor\frac{i}{2}\right\rfloor})$ 最大。输出这个值的最大可能值。

其中， $\otimes$ 表示同或运算。也就是， $1 \otimes 1=1, 0 \otimes 0=1, 1 \otimes 0 = 0, 0 \otimes 1 = 0$ 。

$n$ 为偶数, $n \leq 450,-10^9 \leq A_i \leq 10^9$ 。

题解

由 $\left\lfloor\frac{i}{2}\right\rfloor$ 可以构建二叉树，在二叉树上跑 DP，设 $f_{u,0/1,j}$ 表示 $B_u$ 为 $0/1$ 且子树内有 $j$ 个 $1$ 的方案数。

代码

const int N = 500;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n;
	ll a[N], sz[N];
	ll f[N][2][N << 1], b0 = N;

	void dfs(int u) {
		int ls = u << 1, rs = u << 1 | 1;
		sz[u] = 1;
		if (ls > n) {
			f[u][0][0] = f[u][1][1] = 0;
			return;
		}
		dfs (ls);
		sz[u] += sz[ls];
		if (rs > n) {
			for (int i = 0; i <= sz[ls]; i++) {
				f[u][0][i] = max ({f[ls][1][i], f[ls][0][i] + a[ls], f[u][0][i]});
				f[u][1][i + 1] = max ({f[ls][1][i] + a[ls], f[ls][0][i], f[u][1][i + 1]});
			}
			return;
		}
		dfs (rs);
		sz[u] += sz[rs];
		for (int i = 0; i <= sz[ls]; i++) {
			for (int j = 0; j <= sz[rs]; j++){
				f[u][0][i + j] = max({max(f[ls][1][i], f[ls][0][i] + a[ls]) + max(f[rs][1][j], f[rs][0][j] + a[rs]), f[u][0][i + j]});
				f[u][1][i + j + 1] = max({max(f[ls][0][i], f[ls][1][i] + a[ls]) + max(f[rs][0][j], f[rs][1][j] + a[rs]), f[u][1][i + j + 1]});
			}
		}
	}

	int main () {
		n = Read();
		memset (f, -0x3f, sizeof f);
		for (int i = 1; i <= n; i++) a[i] = Read();
		dfs(1);
		printf ("%lld\n", max(f[1][0][n / 2], f[1][1][n / 2]));
		return 0;
	}
}

int main () {
	freopen("still.in", "r", stdin);
	freopen("still.out", "w", stdout);
	Main::main();
	return 0;
}