摘要: 经典的状态压缩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)。
阅读全文