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