摘要: 经典题型。如果列数较少，就能用我们熟知的状态压缩DP解决。但现在列数有2^31。考虑到相邻两列之间状态转移规则是相同的，我们可以用矩阵表示这种转移规则，而最后的结果就是求这个转移矩阵的n次幂的左上角元素。
阅读全文
摘要: 不错的DP题。状态f[i][x1][y1][x2][y2]表示要把(x1,y1) -- (x2, y2) 分割成i块所得到的最小平方和（平方和指的是每块矩形的和的平方和）。然后根据水平和竖直切割进行状态转移。这样计算出f[n][1][1][8][8]得到整个棋盘分割成n块得到的最小平方和，然后代入均方差公式算得结果。
阅读全文