题目信息

题目类型
提高级
题目年份
2020
题目题型
单选题
关 键 词
最优子序列

题目题干

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

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

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

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

试补全程序。ENl100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
 ENl100150满分答卷(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.     int s = x; 
  13.     while (x) 
  14.     { 
  15.         ①; 
  16.         s++; 
  17.     } 
  18.     return s; 
  19.   
  20. void to_max(LL &x, LL y) 
  21.     if (x < y) 
  22.         x = y; 
  23.   
  24. int main() 
  25.     int n; 
  26.     LL ans = 0; 
  27.     cin >> n; 
  28.     for (int x = 0; x <= MS; x++) 
  29.         for (int y = 0; y <= MS; y++) 
  30.             Max[x][y] = -INF; 
  31.     for (int i = 1; i <= n; i++) 
  32.     { 
  33.         LL a; 
  34.         cin >> a; 
  35.         int x = ②, y = a & MS; 
  36.         LL v = ③; 
  37.         for (int z = 0; z <= MS; z++) 
  38.             to_max(v, ④); 
  39.         for (int z = 0; z <= MS; z++) 
  40.             ⑤; 
  41.         to_max(ans, v); 
  42.     } 
  43.     cout << ans << endl; 
  44.     return 0; 
 

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

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

答案解析

相关题目

第41题 (最优子序列)取 m = 16,给出长度为 n 的整数序列 a1,a2,…,an(0≤ai≤2m)。对于一个二进制数 x,定义其分值 w(x) 为x+popcnt(x),其中 popcnt
第40题 (最优子序列)取 m = 16,给出长度为 n 的整数序列 a1,a2,…,an(0≤ai≤2m)。对于一个二进制数 x,定义其分值 w(x) 为x+popcnt(x),其中 popcnt
第39题 (最优子序列)取 m = 16,给出长度为 n 的整数序列 a1,a2,…,an(0≤ai≤2m)。对于一个二进制数 x,定义其分值 w(x) 为x+popcnt(x),其中 popcnt
第38题 (分数背包)小 S 有 n 块蛋糕,编号从 1 到 n。第 i 块蛋糕的价值是 wi,体积是 vi。他有一个大小为 B 的盒子来装这些蛋糕,也就是说装入盒子的蛋糕的体积总和不能超过 B。
第37题 (分数背包)小 S 有 n 块蛋糕,编号从 1 到 n。第 i 块蛋糕的价值是 wi,体积是 vi。他有一个大小为 B 的盒子来装这些蛋糕,也就是说装入盒子的蛋糕的体积总和不能超过 B。
第36题 (分数背包)小 S 有 n 块蛋糕,编号从 1 到 n。第 i 块蛋糕的价值是 wi,体积是 vi。他有一个大小为 B 的盒子来装这些蛋糕,也就是说装入盒子的蛋糕的体积总和不能超过 B。
第35题 (分数背包)小 S 有 n 块蛋糕,编号从 1 到 n。第 i 块蛋糕的价值是 wi,体积是 vi。他有一个大小为 B 的盒子来装这些蛋糕,也就是说装入盒子的蛋糕的体积总和不能超过 B。
第34题 (分数背包)小 S 有 n 块蛋糕,编号从 1 到 n。第 i 块蛋糕的价值是 wi,体积是 vi。他有一个大小为 B 的盒子来装这些蛋糕,也就是说装入盒子的蛋糕的体积总和不能超过 B。
第33题 #include <iostream>  #include <queue>  using namespace std;      const int maxl = 2
第32题 #include <iostream>  #include <queue>  using namespace std;      const int maxl = 2

提示声明

  • 免责声明:本站资源均来自网络或者用户投稿,仅供用于学习和交流:如有侵权联系删除!
  • 温馨提示:本文属于积分文章,需要充值获得积分或升级VIP会员,也可在会员中心投稿获取。

猜你喜欢