Anyone_1 2010-10-25 08:32:00
点我顶贴
收藏
删除
设f[ i ] 为前 i 个的放置方法,那么:
1.f[ 1 ~ m - 1 ] = 2 ^ i;
2.当i >= m 时, f[ i ] = 2 * f[ i - 1 ];
但是这样就没有判断连续N个相同的情况
那么这种情况的个数是多少呢?
是—— f[ i - ( m - 1 ) ]
也就是说, 在 i - ( m - 1 ) 的所有情况,
最后一个是什么(0/1),就补 m-1 个相同的数(0/1)
所以 f[ i ] = 2 * f[ i -1 ] - f[ i - m + 1 ];
根据这个再构造矩阵乘法,复杂度大概O(log(N)*M^3)
与核电站问题相通,只是少了“不放核物质”这个条件
也就是不能两腿都不卖
这个想法对么?求BS