第42题 （最优子序列）取 m = 16，给出长度为 n 的整数序列 a1,a2,…,an(0≤ai≤2m)。对于一个二进制数 x，定义其分值 w(x) 为x+popcnt(x)，其中 popcnt

第42题ruB100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

（最优子序列）取 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。求一个子序列似的其子序列的分值最大，输出这个最大值。ruB100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输入第一行包含一个整数 n(1≤n≤40000)。接下来一行包含 n 个整数a1,a2,…,an。ruB100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

提示：考虑优化朴素的动态规划算法，将前 m/2 位和后m /2位分开计算。ruB100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

Max[x][y] 表示当前的子序列下一个位置的高 8 位是 x、最后一个位置的低 8 位是 y 时的最大价值。ruB100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

试补全程序。ruB100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
 ruB100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

1. #include <iostream> 
2. using namespace std; 
3. typedef long long LL; 
4. const int MAXN = 40000, M = 16, B = M >> 1, MS = (1 << B) - 1; 
5. const LL INF = 1000000000000000LL; 
6. LL Max[MS + 4][MS + 4]; 
7. int w(int x) 
8. { 
9.     int s = x; 
10.     while (x) 
11.     { 
12.         ①; 
13.         s++; 
14.     } 
15.     return s; 
16. } 
17. void to_max(LL &x, LL y) 
18. { 
19.     if (x < y) 
20.         x = y; 
21. } 
22. int main() 
23. { 
24.     int n; 
25.     LL ans = 0; 
26.     cin >> n; 
27.     for (int x = 0; x <= MS; x++) 
28.         for (int y = 0; y <= MS; y++) 
29.             Max[x][y] = -INF; 
30.     for (int i = 1; i <= n; i++) 
31.     { 
32.         LL a; 
33.         cin >> a; 
34.         int x = ②, y = a & MS; 
35.         LL v = ③; 
36.         for (int z = 0; z <= MS; z++) 
37.             to_max(v, ④); 
38.         for (int z = 0; z <= MS; z++) 
39.             ⑤; 
40.         to_max(ans, v); 
41.     } 
42.     cout << ans << endl; 
43.     return 0; 
44. } 

④ 处应填（ ）ruB100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

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)