写在前面
周赛最后一题，想到dp了，但是状态表示和转移死活想不出来，最后参考零神的题解，总算是自己敲出来了，零神题解讲解的很清楚，我就不在过多解释了，这里只附上题目及代码。
题目
代码
class Solution {
int n;
int m;
int n3;
int[][] maskTrans;//对每一种状态mask转换为3进制
int[] inMask;//状态mask内向的人数
int[] exMask;//状态mask外向的人数
int[] scoreInner;//状态mask对应的行内分数
int[][] scoreOuter;//状态mask1和mask2两者行间的分数
int[][][][] memo;//备忘录
public int getMaxGridHappiness(int m, int n, int in, int ex) {
//初始化变量
this.n = n;
this.m = m;
this.n3 = (int)Math.pow(3, n);
//初始化数组
this.maskTrans = new int[n3][n];
this.inMask = new int[n3];
this.exMask = new int[n3];
this.scoreInner = new int[n3];
this.scoreOuter = new int[n3][n3];
this.memo = new int[n3][m][in + 1][ex + 1];
for(int mask = 0; mask < n3; mask++){
for(int i = 0; i < m; i++){
for(int j = 0; j <= in; j++){
for(int k = 0; k <= ex; k++){
memo[mask][i][j][k] = -1;
}
}
}
}
//预处理
// mask状态与3进制转换
for(int mask = 0; mask < n3; mask++){
int tmp = mask;
for(int i = 0; i < n; i++){
maskTrans[mask][i] = tmp % 3;
tmp /= 3;
}
}
// mask状态对应的内向外向人数、及行内分数
for(int mask = 0; mask < n3; mask++){
for(int i = 0; i < n; i++){
if(maskTrans[mask][i] == 1){
//内向
inMask[mask]++;
scoreInner[mask] += 120;
}else if(maskTrans[mask][i] == 2){
//外向
exMask[mask]++;
scoreInner[mask] += 40;
}else{
continue;
}
//前一个放置了内向或者外向的人
if(i > 0 && maskTrans[mask][i - 1] != 0){
scoreInner[mask] += compute(maskTrans[mask][i], maskTrans[mask][i - 1]);
}
}
}
// mask1 和 mask2 的行间分数
for(int mask1 = 0; mask1 < n3; mask1++){
for(int mask2 = 0; mask2 < n3; mask2++){
for(int i = 0; i < n; i++){
//上下两个人相邻
if(maskTrans[mask1][i] != 0 && maskTrans[mask2][i] != 0){
scoreOuter[mask1][mask2] += compute(maskTrans[mask1][i], maskTrans[mask2][i]);
}
}
}
}
return dfs(0, 0, in, ex);
}
/**
* 计算人物 p1 和 p2 对行内分数的贡献
*/
public int compute(int p1, int p2){
if(p1 == 1 && p2 == 1){
return -60;
}
if(p1 == 2 && p2 == 2){
return 40;
}
return -10;
}
/**
* 上一行为maskLast状态
* 当前为第row行
* 还剩下in个内向的人
* 还剩下ex个外向的人
* 返回这种情况下最大可能的网格幸福感
*/
public int dfs(int maskLast, int row, int in, int ex){
if(row == m || in == 0 && ex == 0){
return 0;
}
//记忆化
if(memo[maskLast][row][in][ex] != -1){
return memo[maskLast][row][in][ex];
}
int res = 0;
for(int mask = 0; mask < n3; mask++){
if(inMask[mask] > in || exMask[mask] > ex)
continue;
res = Math.max(res, scoreInner[mask] + scoreOuter[maskLast][mask] + dfs(mask, row + 1, in - inMask[mask], ex - exMask[mask]));
}
return memo[maskLast][row][in][ex] = res;
}
}
还是第一次遇到3进制的状压DP，也算是学到了些新东西了
如果文章有写的不对的地方还请指出，感恩相遇~
