请问这题为什么会推出这个公式

level 6

sswzfly 楼主

http://acm.tju.edu.cn/toj/showp3552.html
题目大意是警察抓小偷， N个房子，编号为1-N，小偷在其中一个房子里面，警察白天搜查其中一个房子，如果搜到了结束，否则小偷可以在夜里跑到相邻的房子。求在最坏的情况下要抓几天。。公式是2*(n-2)，可是如果警察从1一直搜到N的话不是更少?
求大牛解答~~

2013年08月05日 08点08分 1

level 7

txshs123

注意小偷是会动的，警察今天搜完了这个屋，明天小偷还是有可能跑到这个屋来的。

2013年08月05日 09点08分 3

level 6

sswzfly 楼主

明白了这样搜的原因，但是证明没看懂：每一天我们可以指定某个X[i，j]=S=1，其他X[i,j] = X[i-1，j-1] * X[i-1，j+1]。这个指定的X[i, j]和其他X[i, j]是一样的吗

2013年08月05日 10点08分 4

txshs123

其实这个是从解题报告上扣下来的 [汗]

2013年08月05日 14点08分