摘要: 經典的狀態(tài)壓縮DP。f[i][j]表示第i行，方格排布為二進制數(shù)j（第k位上為1表示凸出一個格子，為0表示不凸出）的方案數(shù)。用DFS進行狀態(tài)轉移。
如果行數(shù)比較多的話，可以用矩陣乘法優(yōu)化。因為每行的狀態(tài)轉移都是相同的。設烈數(shù)為m，行數(shù)為n，可以做到O(2^(3m)logn)。
閱讀全文
摘要: 經典的TSP問題變種。狀態(tài)為f[i][j][k]，表示經過二進制數(shù)i所指的哈密頓路（第bi位為1表示經過該點，為0表示不經過該點），倒數(shù)第二個點為j，最后一個點為k。.value表示最大權值，.num表示能走出最大權值的路徑數(shù)。若圖中k到p有邊，f[i][j][k]則轉移到f[i'][k][p]。i' == i | (1 << p)。
閱讀全文