diff options
author | Jack Sangdahl <[email protected]> | 2024-10-13 10:54:11 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-10-13 10:54:11 -0600 |
commit | 0f3e9ac36b523a36c78981c031f2967e9d878136 (patch) | |
tree | cfab17765c949c87a2a5233207e0efc91bb09867 | |
parent | 9230f76c2ee902e932ea5a0c6b17dbc2740a21ce (diff) | |
download | leetcode-0f3e9ac36b523a36c78981c031f2967e9d878136.tar.gz leetcode-0f3e9ac36b523a36c78981c031f2967e9d878136.zip |
1659. maximise grid happiness
-rw-r--r-- | maximise_grid_happiness.cpp | 66 | ||||
-rw-r--r-- | maximise_grid_happiness.py | 52 |
2 files changed, 118 insertions, 0 deletions
diff --git a/maximise_grid_happiness.cpp b/maximise_grid_happiness.cpp new file mode 100644 index 0000000..612c111 --- /dev/null +++ b/maximise_grid_happiness.cpp @@ -0,0 +1,66 @@ +// 1659. Maximize Grid Happiness +#include "leetcode.h" + +/* + * you are given four integers 'm', 'n', 'introvertsCount', and + * 'extrovertsCount'. you have an 'm * n' grid and there are two types of + * people: introverts and extroverts. there are 'introvertsCount' introverts and + * 'extrovertsCount' extroverts. you should decide how many people ou want to + * live in the grid and assign each of them one grid cell. note that you do not + * have to have all the people living in the grid. neighbours live directly + * adjacent cells, north, east, south, and west of a person's cell. the grid + * happiness is the sum of each person's happiness. return the maximum possible + * grid happiness + */ + +class Solution { +private: + int dp[25][7][7][64][64] = {}; + int n_cost(int m, int n, int i, int j, int introvert_mask, int extrovert_mask, + int d) { + int diff = 0, up = (1 << (n - 1)); + if (j && (introvert_mask & 1)) + diff += d - 30; + if (i && (introvert_mask & up)) + diff += d - 30; + if (j && (extrovert_mask & 1)) + diff += d + 20; + if (i && (extrovert_mask & up)) + diff += d + 20; + return diff; + } + int dfs(int m, int n, int p, int in, int out, int introvert_mask, + int extrovert_mask) { + int i = p / n, j = p % n; + if (i >= m) + return 0; + if (dp[p][in][out][introvert_mask][extrovert_mask]) + return dp[p][in][out][introvert_mask][extrovert_mask] - 1; + int n_introvert_mask = (introvert_mask << 1) & 63, + n_extrovert_mask = (extrovert_mask << 1) & 63; + int res = dfs(m, n, p + 1, in, out, n_introvert_mask, n_extrovert_mask); + if (in) { + int diff = n_cost(m, n, i, j, introvert_mask, extrovert_mask, -30) + 120; + res = max(res, diff + dfs(m, n, p + 1, in - 1, out, n_introvert_mask + 1, + n_extrovert_mask)); + } + if (out) { + int diff = n_cost(m, n, i, j, introvert_mask, extrovert_mask, 20) + 40; + res = max(res, diff + dfs(m, n, p + 1, in, out - 1, n_introvert_mask, + n_extrovert_mask + 1)); + } + return res; + } + +public: + int getMaxGridHappiness(int m, int n, int introvertsCount, + int extrovertsCount) { + return dfs(m, n, 0, introvertsCount, extrovertsCount, 0, 0); + } +}; + +int main() { + Solution obj; + printf("%d\n", obj.getMaxGridHappiness(2, 3, 1, 2)); // expect: 240 + printf("%d\n", obj.getMaxGridHappiness(3, 1, 2, 1)); // expect: 260 +} diff --git a/maximise_grid_happiness.py b/maximise_grid_happiness.py new file mode 100644 index 0000000..d1cc114 --- /dev/null +++ b/maximise_grid_happiness.py @@ -0,0 +1,52 @@ +# 1659. Maximize Grid Happiness + +""" +you are given four integers 'm', 'n', 'introvertsCount', and +'extrovertsCount'. you have an 'm * n' grid and there are two types of +people: introverts and extroverts. there are 'introvertsCount' introverts and +'extrovertsCount' extroverts. you should decide how many people ou want to +live in the grid and assign each of them one grid cell. note that you do not +have to have all the people living in the grid. neighbours live directly +adjacent cells, north, east, south, and west of a person's cell. the grid +happiness is the sum of each person's happiness. return the maximum possible +grid happiness +""" + + +class Solution(object): + def getMaxGridHappiness(self, m, n, introvertsCount, extrovertsCount): + """ + :type m: int + :type n: int + :type introvertsCount: int + :type extrovertsCount: int + :rtype: int + """ + ing, exg, inl, exl = 120, 40, -30, 20 + valid = [[0, 0, 0], [0, 2 * inl, inl + exl], [0, inl + exl, 2 * exl]] + + def dp(idx, row, i, e): + if idx == -1: + return 0 + r, c, res = idx // n, idx % n, [] + n = [(1, i - 1, e, ing), (2, i, e - 1, exg), (0, i, e, 0)] + for val, dx, dy, gain in n: + tmp = 0 + if dx >= 0 and dy >= 0: + tmp = dp(idx - 1, (val,) + row[:-1], dx, dy) + gain + if c < n - 1: + tmp += valid[val][row[0]] + if r < m - 1: + tmp += valid[val][row[-1]] + res.append(tmp) + return max(res) + + if m < n: + n = n, m + return dp(m * n - 1, tuple([0] * n), introvertsCount, extrovertsCount) + + +if __name__ == "__main__": + obj = Solution() + print(obj.getMaxGridHappiness(m=2, n=3, introvertsCount=1, extrovertsCount=2)) + print(obj.getMaxGridHappiness(m=3, n=1, introvertsCount=2, extrovertsCount=1)) |