3287. 求出数组中最大序列值

发表于 分类于 阅读次数： Waline： 本文字数： 645 阅读时长 ≈ 2 分钟

考点

  • 01背包

思路

本题难在设计代码，思路不难，直接看第一版代码吧，转移方程写在注释里了

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
class Solution {
 public:
  int n;
  bool pre[455][455][128], suf[455][455][128];
  int maxValue(vector<int>& nums, int K) {
    n = nums.size();
    //  前缀DP
    // pre[i][j][k]：前i个数，构成长度为j的序列，异或值为k的可行性
    // 求当前状态去更新其他状态，而非求当前状态由哪些状态更新，因为或运算没有可减性
    // 初值为pre[0]，用来更新pre[1]
    memset(pre, 0, sizeof(pre));
    pre[0][0][0] = 1;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j <= min(K, i); ++j) {
        for (int k = 0; k < (1 << 7); ++k) {
          if (!pre[i][j][k]) continue;
          pre[i + 1][j][k] = 1;
          if (j + 1 <= K) pre[i + 1][j + 1][k | nums[i]] = 1;
        }
      }
    }
    // 后缀DP
    // suf[i][j][k]：下标i ~ n - 1的范围中，构成长度为j的序列，异或值为k的可行性
    memset(suf, 0, sizeof(suf));
    suf[n][0][0] = 1;
    for (int i = n; i >= 1; --i) {
      for (int j = 0; j <= min(K, (n - 1) - i + 1); ++j) {
        for (int k = 0; k < (1 << 7); ++k) {
          if (!suf[i][j][k]) continue;
          suf[i - 1][j][k] = 1;
          if (j + 1 <= K) suf[i - 1][j + 1][k | nums[i - 1]] = 1;
        }
      }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
      for (int x = 0; x < (1 << 7); ++x) {
        for (int y = 0; y < (1 << 7); ++y) {
          if (pre[i][K][x] && suf[i][K][y]) ans = max(ans, x ^ y);
        }
      }
    }
    return ans;
  }
};

但是这份代码超时，需要滚动数组降维，需要注意的点也写在注释里了：

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
class Solution {
 public:
  int n;
  static const int maxn = 4e2 + 50, maxm = (1 << 7);
  bool pre[maxn][maxm], suf[maxn][maxm];
  // preK[i][j]：pre数组在序列长度为K下的快照
  // sufK[i][j]：suf数组在序列长度为K下的快照
  bool preK[maxn][maxm], sufK[maxn][maxm];
  int maxValue(vector<int>& nums, int K) {
    n = nums.size();
    memset(pre, 0, sizeof(pre)), memset(preK, 0, sizeof(preK));
    pre[0][0] = 1;
    for (int i = 0; i < n; ++i) {
      // 注意j必须倒序，这里k可以不用倒序
      for (int j = min(K - 1, i); j >= 0; --j) {
        for (int k = 0; k < (1 << 7); ++k) {
          if (pre[j][k]) pre[j + 1][k | nums[i]] = 1;
        }
      }
      // 记录快照
      if (i + 1 >= K) {
        for (int j = 0; j < (1 << 7); ++j) preK[i + 1][j] = pre[K][j];
      }
    }
    memset(suf, 0, sizeof(suf)), memset(sufK, 0, sizeof(sufK));
    suf[0][0] = 1;
    for (int i = n; i >= 1; --i) {
      for (int j = min(K - 1, n - i); j >= 0; --j) {
        for (int k = 0; k < (1 << 7); ++k) {
          if (suf[j][k]) suf[j + 1][k | nums[i - 1]] = 1;
        }
      }
      // 记录快照
      if (n - i + 1 >= K) {
        for (int j = 0; j < (1 << 7); ++j) sufK[i - 1][j] = suf[K][j];
      }
    }
    int ans = 0;
    for (int i = K; i <= n - K; ++i) {
      for (int x = 0; x < (1 << 7); ++x) {
        if (preK[i][x])
          for (int y = 0; y < (1 << 7); ++y) {
            if (sufK[i][y]) ans = max(ans, x ^ y);
          }
      }
    }
    return ans;
  }
};