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