警钟长鸣
查看原帖
警钟长鸣
1033360
retamian楼主2023/10/26 20:35

如果你是这样 dp 的(DFS枚举所有行的状态,对于每个状态跑2维DP实际上是同样的做法)

int dp[N][N][1 << 15]; //从前i行选,选j行,状态为state 子矩阵最小分值

这样是不能正确转移的,在枚举上一行 kk 的时候不能保证dp[k][j][state]一定选择了第 kk 行,导致转移错误

正确的方式应该是:

int dp[N][N][1 << 15]; //从前i行选且选择第i行,选j行,状态为state 子矩阵最小分值

这样在求出答案后枚举每一个dp[i][m][state]( mm是题目给的)取最小就是答案。

2023/10/26 20:35
加载中...