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
|
// 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
}
|