(最优子序列)取m=6,给出长度为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时的最大价值。
试补全程序。
#inelude <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; }
①处应填( )
x >>= 1
x ^= x &(x ^ (x + 1))
x -= x | -x
x ^= x &(x ^ (x - 1))
②处应填( )
(a & MS) << B
a >> B
a & (1 << B)
a & (MS << B)
③处应填( )
-INF
Max[y][x]
0
Max[x][y]
④处应填( )
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)
⑤处应填 ( )
to_max(Max[y][z], v + w(a ^ (z << B)))
to_max(Max[z][y], v + w((x ^ z) << B))
to_max(Max[z][y], v + w(a ^ (z << B)))
to_max(Max[x][z], v + w(y ^ z))