(最优子序列)取 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接下来一行包含 n个整数 a1,a2,⋯,an。
提示:考虑优化朴素的动态规划算法,将前 \(\frac{m}{2}\) 位和后 \(\frac{m}{2}\)位分开计算。
Max[x][y]
表示当前的子序列下一个位置的高 8 位是 x、最后一个位置的低 8 位是 y 时的最大价值。
试补全程序。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 | #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; } |
0 of 5 Questions completed
Questions:
You have already completed the quiz before. Hence you can not start it again.
Quiz is loading…
You must sign in or sign up to start the quiz.
You must first complete the following:
0 of 5 Questions answered correctly
Your time:
Time has elapsed
You have reached 0 of 0 point(s), (0)
Earned Point(s): 0 of 0, (0)
0 Essay(s) Pending (Possible Point(s): 0)
1、①处应填( )
2、②处应填( )
3、③处应填( )
4、④处应填( )
5、⑤处应填( )