讨论 / 这题一点思路~
Anyone_1 2010-10-25 23: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

#1 Anyone_1@2010-10-25 23:32:00
回复 删除
这题原来的题解也太复杂了,我根本就confused了
查看更多回复
提交回复