摘要: 經典題型。如果列數較少，就能用我們熟知的狀態壓縮DP解決。但現在列數有2^31。考慮到相鄰兩列之間狀態轉移規則是相同的，我們可以用矩陣表示這種轉移規則，而最后的結果就是求這個轉移矩陣的n次冪的左上角元素。
閱讀全文
摘要: 不錯的DP題。狀態f[i][x1][y1][x2][y2]表示要把(x1,y1) -- (x2, y2) 分割成i塊所得到的最小平方和（平方和指的是每塊矩形的和的平方和）。然后根據水平和豎直切割進行狀態轉移。這樣計算出f[n][1][1][8][8]得到整個棋盤分割成n塊得到的最小平方和，然后代入均方差公式算得結果。
閱讀全文