第40题
（最优子序列）取 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。求一个子序列似的其子序列的分值最大，输出这个最大值。
输入第一行包含一个整数 n(1≤n≤40000)。接下来一行包含 n 个整数a1,a2,…,an。
提示：考虑优化朴素的动态规划算法，将前 m/2 位和后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 = 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;
- }
② 处应填（ ）
