问题：
给定m*n的格子，每个格子可以住人。
给定introvertsCount个内向的人，extrovertsCount个外向的人。
求分配所有人的住法，使得快乐值最大。
其中快乐值：
- 一个内向的人，初始快乐值=120
- 一个外向的人，初始快乐值=40
- 内向人周围多一个邻居，快乐值-30
- 外向人周围多一个邻居，快乐值+20
Example 1: Input: m = 2, n = 3, introvertsCount = 1, extrovertsCount = 2 Output: 240 Explanation: Assume the grid is 1-indexed with coordinates (row, column). We can put the introvert in cell (1,1) and put the extroverts in cells (1,3) and (2,3). - Introvert at (1,1) happiness: 120 (starting happiness) - (0 * 30) (0 neighbors) = 120 - Extrovert at (1,3) happiness: 40 (starting happiness) + (1 * 20) (1 neighbor) = 60 - Extrovert at (2,3) happiness: 40 (starting happiness) + (1 * 20) (1 neighbor) = 60 The grid happiness is 120 + 60 + 60 = 240. The above figure shows the grid in this example with each person's happiness. The introvert stays in the light green cell while the extroverts live on the light purple cells. Example 2: Input: m = 3, n = 1, introvertsCount = 2, extrovertsCount = 1 Output: 260 Explanation: Place the two introverts in (1,1) and (3,1) and the extrovert at (2,1). - Introvert at (1,1) happiness: 120 (starting happiness) - (1 * 30) (1 neighbor) = 90 - Extrovert at (2,1) happiness: 40 (starting happiness) + (2 * 20) (2 neighbors) = 80 - Introvert at (3,1) happiness: 120 (starting happiness) - (1 * 30) (1 neighbor) = 90 The grid happiness is 90 + 80 + 90 = 260. Example 3: Input: m = 2, n = 2, introvertsCount = 4, extrovertsCount = 0 Output: 240 Constraints: 1 <= m, n <= 5 0 <= introvertsCount, extrovertsCount <= min(m * n, 6)
example 1
解法：DFS，Backtracking（回溯算法），DP
状态：
- 当前位置 p （x，y）【p=x*n+y，x=p/n, y=p%n】
- 剩下人数：
- 内向人数：ic
- 外向人数：ec
- 到目前位置为止，住人情况：
- 内向人：imap
- 外向人：emap
选择：
- 不住人nobody
- 快乐值=下一个位置的快乐值。
- 状态变化：p+1，ic，ec，(imap<<1)，(emap<<1)
- 住内向的人
- 快乐值=120+（消耗自己-30+消耗/快乐左边人+消耗/快乐上边人）+下一个位置的快乐值。
- 状态变化：p+1，ic-1，ec，(imap<<1)+1，(emap<<1)
- 住外向的人
- 快乐值=40+ （快乐自己+20+消耗/快乐左边人+消耗/快乐上边人）+下一个位置的快乐值。
- 状态变化：p+1，ic，ec-1，(imap<<1)，(emap<<1)+1
递归退出条件：
- x>=m：返回0。
- 已经求过当前状态的dp，直接返回这个值。
另外，根据当前位置的状态，求影响他人的快乐值nCost（上边蓝色的部分）：
找到在imap和emap中，
- 当前p的上面up位置：1<<(n-1)
- 当前p的左面left位置：1
判断上面位置：（首先有上面的位置：y>0）
- 住了内向人：(imap & up) == 1 ? -> 自己的cost + 这个人的cost(-30)
- 住了外向人：(emap & up) == 1 ? -> 自己的cost + 这个人的cost(+20)
判断左面位置：（首先有左面的位置：x>0）
- 住了内向人：(imap & left) == 1 ? -> 自己的cost + 这个人的cost(-30)
- 住了外向人：(emap & left) == 1 ? -> 自己的cost + 这个人的cost(+20)
代码参考：
1 class Solution { 2 public: 3 int dp[25][7][7][64][64]={}; 4 int nCost(int& m, int& n, int& x, int& y, int& imap, int& emap, int selfdiff) { 5 int left = 1, up = 1<<(n-1); 6 int cost = 0; 7 if(y>0 && (imap&left)>0) { 8 cost += (selfdiff-30); 9 } 10 if(x>0 && (imap&up)>0) { 11 cost += (selfdiff-30); 12 } 13 if(y>0 && (emap&left)>0) { 14 cost += (selfdiff+20); 15 } 16 if(x>0 && (emap&up)>0) { 17 cost += (selfdiff+20); 18 } 19 return cost; 20 } 21 22 int dfs(int& m, int& n, int ic, int ec, int p, int imap, int emap) { 23 int x = p/n, y = p%n; 24 if(x>=m) return 0; 25 if(dp[p][ic][ec][imap][emap]) return dp[p][ic][ec][imap][emap]; 26 int imap_cur = (imap<<1)&63; 27 int emap_cur = (emap<<1)&63; 28 //cur position: nobody 29 int res = dfs(m, n, ic, ec, p+1, imap_cur, emap_cur); 30 //cur position: introvert 31 if(ic>0) { 32 int diff = 120 + nCost(m, n, x, y, imap, emap, -30); 33 res = max(res, diff + dfs(m, n, ic-1, ec, p+1, imap_cur+1, emap_cur)); 34 } 35 //cur position: extrovert 36 if(ec>0) { 37 int diff = 40 + nCost(m, n, x, y, imap, emap, 20); 38 res = max(res, diff + dfs(m, n, ic, ec-1, p+1, imap_cur, emap_cur+1)); 39 } 40 dp[p][ic][ec][imap][emap] = res; 41 return res; 42 } 43 int getMaxGridHappiness(int m, int n, int introvertsCount, int extrovertsCount) { 44 //dp[x*n+y][ic][ec][imap][emap] 45 46 return dfs(m, n, introvertsCount, extrovertsCount, 0, 0, 0); 47 } 48 };