2007年9月12日

[动态规划]pku1038

摘要: 经典的状态压缩DP，《算法艺术与信息学竞赛》的例题。f[i][j]表示前i行，最后两行状态为二进制数j，嵌入的最多芯片数。第i行到第i+1行用DFS进行状态转移。
由于第i+1行只和第i行有关，故可以用滚动数组优化。

阅读全文

posted @ 2007-09-12 20:44 Felicia 阅读(1505) | 评论 (3) | 编辑收藏