（最优子序列）取m=6，给出长度为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时的最大价值。
试补全程序。
#inelude <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;
}
①处应填（ ）
x >>= 1
x ^= x &(x ^ (x + 1))
x -= x | -x
x ^= x &(x ^ (x - 1))
②处应填（ ）
(a & MS) << B
a >> B
a & (1 << B)
a & (MS << B)
③处应填（ ）
-INF
Max[y][x]
0
Max[x][y]
④处应填（ ）
Max[x][z] + w(y ^ z)
Max[x][z] + w(a ^ z)
Max[x][z] + w(x ^ (z << B))
Max[x][z] + w(x ^ z)
⑤处应填 ( )
to_max(Max[y][z], v + w(a ^ (z << B)))
to_max(Max[z][y], v + w((x ^ z) << B))
to_max(Max[z][y], v + w(a ^ (z << B)))
to_max(Max[x][z], v + w(y ^ z))