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