【每日一题Day246】LC1659最大化网格幸福感 | 状压dp

*最大化网格幸福感【LC1659】

给你四个整数 m、n、introvertsCount 和 extrovertsCount 。有一个 m x n 网格，和两种类型的人：内向的人和外向的人。总共有 introvertsCount 个内向的人和 extrovertsCount 个外向的人。

请你决定网格中应当居住多少人，并为每个人分配一个网格单元。 注意，不必 让所有人都生活在网格中。

每个人的 幸福感 计算如下：

• 内向的人 开始 时有 120 个幸福感，但每存在一个邻居（内向的或外向的）他都会 失去 30 个幸福感。
• 外向的人 开始 时有 40 个幸福感，每存在一个邻居（内向的或外向的）他都会 得到 20 个幸福感。

邻居是指居住在一个人所在单元的上、下、左、右四个直接相邻的单元中的其他人。

网格幸福感 是每个人幸福感的 总和 。 返回 最大可能的网格幸福感 。

好难 了解一下

状压dp+按行

• 思路

  朴素的dfs会超时，由于每个位置只有「空」「内向」「外向」三种状态，因此可以将这三个状态分别编码为 0,1,2，并用一个长度（位数）为 n 的三进制数对一行的状态进行编码，用状压dp解决。

  • 子问题：如果按行处理的话，枚举每一行的状态得到的最大分数，每一行的分数分为「行内分数」和「行外分数」

    • 「行内分数」：在同一行内每个人的分数，内向 120分，外向 40分；以及由于两人相邻（在同一行内，即左右相邻）贡献的额外分数，两个内向 −60分，两个外向 40 分，其余情况 −10分；

    • 「行外分数」：由于两人相邻（在不同行内，即上下相邻）贡献的额外分数，同理为 −60,40,−10分中的一种。

    • 递归的过程中有四个变量：当前选择的行、前一行的状态码、可供选择的内向的人和外向的人的个数，因此在记忆化需要用四维memo记录

  • 递归函数定义：

    令 $f({\text{mask}}_L,\text{row}$, 表示当我们枚举到第 $row$行且之前的行已经枚举完成，第 $\text{row}-1$行的状态为 $\text{mask}$ ，还剩余 $nx$个内向的人以及 $\text{wx}$ 个外向的人的情况下，从第 $row$ 行开始往后的所有行可以获得的最大分数。

  • 状态转移

    枚举第 $\text{row}$ 行的状态 $\text{mask}$，计算「行内分数」以及「行外分数」，并扣除该行分别使用的内向和外向的人数，再转移到下一行。
    KaTeX parse error: Expected 'EOF', got '&' at position 2: &̲ f(mask_L,row,n…

    • ${\text{count}}_{\text{nx}}(mask)$表示状态 $mask$ 中有多少个内向的人，即有多少个 1；
    • ${\text{count}}_{\text{wx}}(mask)$ 表示状态$\text{mask}$中有多少个外向的人，即有多少个 2；
    • ${\text{score}}_{\text{inner}}(mask)$ 表示状态 $mask\text{mask}mask$ 的「行内分数」；
    • ${\text{score}}_{\text{outer}}(\text{mask},{\text{mask}}_L$ ) 表示状态 $\text{mask}$和 ${\text{mask}}_L$ 之间的「行外分数」。

  • 递归边界

    • 剩余可以选择的人数为0时，返回0
    • $row=m$时，返回0

• 实现

  class Solution {
      private int m;
      private int mx;
      private int[] f;
      private int[][] g;// 记录每个位置的消息
      private int[][] bits;
      private int[] ix;
      private int[] ex;
      private Integer[][][][] memo;
      private final int[][] h = {{0, 0, 0}, {0, -60, -10}, {0, -10, 40}};
  
      public int getMaxGridHappiness(int m, int n, int introvertsCount, int extrovertsCount) {
          this.m = m;
          mx = (int) Math.pow(3, n);// 三进制枚举的最大值
          f = new int[mx];// 行内分数
          g = new int[mx][mx];// 行间分数
          bits = new int[mx][n];// mask中第i列的比特值
          ix = new int[mx];// mask中内向人的个数
          ex = new int[mx];// mask中外向人的个数
          memo = new Integer[m][mx][introvertsCount + 1][extrovertsCount + 1];
          for (int i = 0; i < mx; ++i) {
              int mask = i;
              for (int j = 0; j < n; ++j) {
                  int x = mask % 3;// 状态值
                  mask /= 3;
                  bits[i][j] = x;
                  if (x == 1) {
                      ix[i]++;
                      f[i] += 120;
                  } else if (x == 2) {
                      ex[i]++;
                      f[i] += 40;
                  }
                  if (j > 0) {
                      f[i] += h[x][bits[i][j - 1]];
                  }
              }
          }
          for (int i = 0; i < mx; ++i) {
              for (int j = 0; j < mx; ++j) {
                  for (int k = 0; k < n; ++k) {
                      g[i][j] += h[bits[i][k]][bits[j][k]];
                  }
              }
          }
          return dfs(0, 0, introvertsCount, extrovertsCount);
      }
  
      private int dfs(int i, int pre, int ic, int ec) {
          if (i == m || (ic == 0 && ec == 0)) {
              return 0;
          }
          if (memo[i][pre][ic][ec] != null) {
              return memo[i][pre][ic][ec];
          }
          int ans = 0;
          for (int cur = 0; cur < mx; ++cur) {
              if (ix[cur] <= ic && ex[cur] <= ec) {
                  ans = Math.max(ans, f[cur] + g[pre][cur] + dfs(i + 1, cur, ic - ix[cur], ec - ex[cur]));
              }
          }
          return memo[i][pre][ic][ec] = ans;
      }
  }
  
  作者：ylb
  链接：https://leetcode.cn/problems/maximize-grid-happiness/solutions/2318399/python3javacgotypescript-yi-ti-shuang-ji-fssp/
  来源：力扣（LeetCode）
  著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
  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
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63
  64
  65
  66
  67
  68
  69

轮廓线dp

https://leetcode.cn/problems/maximize-grid-happiness/solutions/2318399/python3javacgotypescript-yi-ti-shuang-ji-fssp/