第39~43题题目

（最优子序列）取m = 16，给出长度为n的整数序列a1, a2,…, an(0≤ ai <2m)。对于一个二进制数x，定义其分值w(x)为x+ popcnt(x)，其中popcnt(x)表示x二进制表示中1的个数。对于一个子序列b1, b2…, bk，定义其子序列分值S为w(b1 ⊕ b2) + w(b2 ⊕b3)+w(b3 ⊕ b4)+…+w(bk-1 ⊕ bk)。其中⊕表示按位异或。对于空子序列，规定其子序

列分值为0。求一个子序列使得其子序列分值最大，输出这个最大值。输入第一行包含一个整数n(1 ≤n ≤ 40000)。接下来一行包含n个整数a1, a2,…, an。

提示：考虑优化朴素的动态规划算法，将前m/2位和后m/2位分开计算。Max[x][y]表示当前的子序列下一个位置的高8位是x、最后一个位置的低8位是y时的最大价值。

试补全程序。

#include<iostream>

using namespace std;

typedef long long LL;

const int MAXN = 40000, M = 16, B = M >> 1, MS = (1 << B) - 1;
const LL INF = 1000000000000000LL;
LL Max[MS + 4][MS + 4];

int w(int x) {
	int s = x;
	while(x) {
		①;
		s++;
	}
	return s;
}

void to_max(LL &x, LL y) {
	if(x < y)
		x = y;
}

int main() {
	int n;
	LL ans = 0;
	cin >> n;
	for(int x = 0; x <= MS; x++)
		for(int y = 0; y <= MS; y++)
			Max[x][y] = -INF;
	for(int i = 1; i <= n ; i++) {
		LL a;
		cin >> a;
		int x = ② , y = a & MS;
		LL v = ③;
		for(int z = 0; z < = MS; z++)
			to_max(v, ④);
		for(int z = 0; z < = MS; z++)
			⑤;
		to_max(ans , v);
	}
	cout << ans << endl;
	return 0;
}

①处应填（）