1726: CSP-S20最优子序列（完善程序）

（最优子序列）取 m=16，给出长度为 n 的整数序列 a(1),a(2),…,a(n)(0≤a(i)<2^m)。对于一个二进制数 x，定义其分值 w(x) 为 x+popcnt(x)，其中 popcnt(x) 表示 x 二进制表示中 1 的个数。对于一个子序列 b(1),b(2),…,b(k)，定义其子序列分值 S 为 w(b(1)⊕b(2))+w(b(2)⊕b(3))+w(b(3)⊕b(4))+⋯+w(b(k−1)⊕b(k))。其中 ⊕ 表示按位异或。对于空子序列，规定其子序列分值为 0 求一个子序列使得其子序列分值最大，输出这个最大值。

输入第一行包含一个整数 n(1≤n≤40000) 接下来一行包含 n 个整数 a(1),a(2),⋯,a(n)。

提示：考虑优化朴素的动态规划算法，将前 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;
}

    1. ①处应填（ ）
    A.    x >>= 1
    B.    x ^= x &(x ^ (x + 1))
    C.    x -= x | -x
    D.    x ^= x &(x ^ (x - 1))

    2. ②处应填（ ）
    A.    (a & MS) << B
    B.    a >> B
    C.    a & (1 << B)
    D.    a & (MS << B)

    3. ③处应填（ ）
    A.    -INF
    B.    Max[y][x]
    C.    0
    D.    Max[x][y]

    4. ④处应填（ ）
    A.    Max[x][z] + w(y ^ z)
    B.    Max[x][z] + w(a ^ z)
    C.    Max[x][z] + w(x ^ (z << B))
    D.    Max[x][z] + w(x ^ z)

    5. ⑤处应填（ ）
    A.    to_max(Max[y][z], v + w(a ^ (z << B)))
    B.    to_max(Max[z][y], v + w((x ^ z) << B))
    C.    to_max(Max[z][y], v + w(a ^ (z << B)))
    D.    to_max(Max[x][z], v + w(y ^ z))