(最优子序列) 取m= 16，给出长度为n的整数序列$(0 \leq a_i < 2^m)$。对于一个二进制数x，定义其分值w(x)为x + popcnt(x)，其中popcnt(x)表示x二进制表示中1的个数。对于一个子序列$b_1,b_2,\ldots,b_k$，定义其子序列分值S为$w(b_1 \oplus b2) + w(b2 \oplus b3) + w(b3 \oplus b4) +...+ w(b_{k-1} \oplus b_k)$。其中$\oplus$表示按位异或。对于空子序列，规定其子序列分值为0。求一个子序列使得其子序列分值最大，输出这个最大值。 输入第一行包含一个整数 $n(1 ≤n≤40000)$。接下来一行包含n个整数$a_1,a_2,\ldots,a_n$。 提示:考虑优化朴素的动态规划算法，将前$\frac{m}{2}$位和后$\frac{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 = 100000000000000LL ;
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;
}