(最优子序列) 取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;


}

选择题