Felicia

2007年9月30日

[动态规划]pku1185
     摘要: 经典的状态压缩DP，状态是f[i][j]，表示第i行，以3进制j为状态。j的位代表一个格子，只能是：0表示第i行和第i - 1行都没有炮兵，1表示第i行没有炮兵而第i-1行有炮兵，2表示第i行有炮兵。然后用DFS进行状态转移。一开始我做了超时，后来预处理了一下合法状态，快了不少，才AC。

  阅读全文
posted @ 2007-09-30 22:09 Felicia 阅读(1042) | 评论 (0) | 编辑 收藏
 
Powered by:
C++博客
Copyright © Felicia