Poj2411 Mondriaan's Dream 给出一个n*m的矩形,然后用1*2大小的多米若骨牌去填充n*m的这个矩形,问有多少种填充方法。 分析:典型的轮廓线动态规划题目。详见刘汝佳新书:算法竞赛入门经典:训练指南P384. 首先本题目是以一个一个的格子为基础来计算状态的,即每次都是考虑当前位置的格子如何放左上骨牌(以当前位置为最右下角,即只不放,左放,和上放3种情况,没有右放和下放)。且本题的状态都是一条一条的轮廓线。如图: 1 1 1 1 1 1 1 K4 K3 K2 K1 K0 O   &n…

2014年2月19日 0条评论 1点热度 阅读全文