diff options
Diffstat (limited to 'maximise_grid_happiness.cpp')
-rw-r--r-- | maximise_grid_happiness.cpp | 66 |
1 files changed, 0 insertions, 66 deletions
diff --git a/maximise_grid_happiness.cpp b/maximise_grid_happiness.cpp deleted file mode 100644 index 612c111..0000000 --- a/maximise_grid_happiness.cpp +++ /dev/null @@ -1,66 +0,0 @@ -// 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 -} |