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

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

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

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

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

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

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

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

x >>= 1

x ^= x & (x ^ (x + 1))

x -= x | -x

x ^= x & (x ^ (x - 1))