题目很有意思就是oj太烂了
刘汝佳的代码太优雅了,看不懂但意思差不多。
就我做过的状压dp总是以一行(或一列)为一个状态先理清一行中的关系,后再找行对行的關系
这里不能用行行之间的关系不够了,因为要考虑不同的放法
那一行不够,两行够不够我觉得够,但时间复杂度不够优秀会包含很多无效转态所以优化一下?
若dp[cur][state]合理那么转移到另一个合理状态。
1.(上)考虑当前放竖着的块
前提:上方的状态为0(没放)并且 现在鈈是第一行
2.(不放)考虑当前没有以(i,j)为右下角的块
前提:上方是1(上方不能为0吧)
3.(左)。。差不多