我们看到这题里的维度m和n出奇地小，竟然不超过5，就有预感算法可能和暴力枚举有关，必然不用考虑去人工设计最优解。
分析矩阵的每个位置有三种可能：不放人、内向人、外向人，因此25个格子的话就会有3^25种可能，这个数据量仍然太大。这个时候我发现3^5=243很小，立刻想到了类似1349. Maximum Students Taking Exam的做法，就是以整行为状态进行枚举，似乎是个可行的思路：因为当前行某种状态对应的最优值，只与上一行状态有关（也就是内向人、外向人的各种相邻关系），而与再前一行就无关了。
于是首先就能想到设计dp[i][state]，表示第i行的安排为state时能够得到的最优值，其中state是一个三进制的整数，每个bit上为0时表示不放人，为1时表示放外向人，为2时表示放内向人。状态转移方程就是考察当前行状态state与上一行状态prevState之间的制约关系。即
for (int i=1; i<=m; i++)
for (int state = 0; state < (1<<m); state++)
{
for (int prevState = 0; prevState < (1<<m); prevState++)
dp[i][state] = max(dp[i][state] + addVal(prevState, state);
}
其中addVal(prevState, state)表示在前一行是prevState的方案的基础上，当前行安排为state的话，可以增加多少价值。这些价值的来源产生自这些：
- 当前行的外向人基本分，如果左、上、右有人相邻的话，额外加分
- 当前行的内向人基本分，如果左、上、右有人相邻的话，额外减分
- 上一行的外向人如果下邻居有人，那么要额外加分
- 上一行的内向人如果下邻居有人，那么要额外减分
但是以上的算法有一个漏洞，那就是我们有外向人、内向人总人数的制约。dp[i][state]并不能看出外向人、内向人的总人数是否已经爆了。所以我们要额外增加两个维度x,y，用dp[i][x][y][state]表示当前第i行采用state的方案，并且截止目前外向人总数是x、内向人总数是y时，能够收获的最大值。因此更新dp[i][x][y][state]时，要先计算出当前行的外向人和内向人的人数a与b，仅枚举合法的dp[i-1][x-a][y-b][prevState]来更新dp[i][x][y][state]。其中要求x>=a，y>=b。
最终的答案是遍历到最后一行时dp[m][x][x][x]的最大值，其中x都可以任意。