1659.最大化网格幸福感.md

1659.最大化网格幸福感

/*
 * @lc app=leetcode.cn id=1659 lang=typescript
 *
 * [1659] 最大化网格幸福感
 */

// @lc code=start
function getMaxGridHappiness(m: number, n: number, introvertsCount: number, extrovertsCount: number): number {}
// @lc code=end

解法 1: 记忆化搜索

function getMaxGridHappiness(m: number, n: number, introvertsCount: number, extrovertsCount: number): number {
  const max = (1 << n) - 1,
    cnt = new Array(1 << n).fill(0)
  for (let i = 0; i < 1 << n; i++) for (let j = 0; j < n; j++) if (i & (1 << j)) cnt[i]++
  const cache: number[][][][][] = Array.from({ length: m }, () =>
    Array.from({ length: 1 << n }, () =>
      Array.from({ length: 1 << n }, () => Array.from({ length: introvertsCount + 1 }, () => [])),
    ),
  )
  const dfs = (index: number, prea: number, preb: number, a: number, b: number): number => {
    if (!a && !b) return 0
    if (index === m) return 0
    if (cache[index][prea][preb][a][b] === undefined) {
      let res = -Infinity,
        s = prea | preb
      for (let i = 0; i <= max; i++) {
        if (cnt[i] > a) continue
        for (let j = 0; j <= max; j++) {
          if (cnt[j] > b) continue
          if (i & j) continue
          let ans = cnt[i] * 120 + cnt[j] * 40
          const s1 = i | j
          ans -= (cnt[i & s] + cnt[i & (s1 >> 1)] + cnt[i & (s1 << 1)] + cnt[prea & s1]) * 30
          ans += (cnt[j & s] + cnt[j & (s1 >> 1)] + cnt[j & (s1 << 1)] + cnt[preb & s1]) * 20
          res = Math.max(res, dfs(index + 1, i, j, a - cnt[i], b - cnt[j]) + ans)
        }
      }
      cache[index][prea][preb][a][b] = res
    }
    return cache[index][prea][preb][a][b]
  }
  return dfs(0, 0, 0, introvertsCount, extrovertsCount)
}

Case

test.each([
  { input: { m: 3, n: 1, introvertsCount: 1, extrovertsCount: 3 }, output: 230 },
  { input: { m: 2, n: 3, introvertsCount: 1, extrovertsCount: 2 }, output: 240 },
  { input: { m: 3, n: 1, introvertsCount: 2, extrovertsCount: 1 }, output: 260 },
  { input: { m: 2, n: 2, introvertsCount: 4, extrovertsCount: 0 }, output: 240 },
])(
  'input: m = $input.m, n = $input.n, introvertsCount = $input.introvertsCount, extrovertsCount = $input.extrovertsCount',
  ({ input: { m, n, introvertsCount, extrovertsCount }, output }) => {
    expect(getMaxGridHappiness(m, n, introvertsCount, extrovertsCount)).toEqual(output)
  },
)