题意:
如图,一列未知的区域长度为n(≤1000),给出第二列的数字,求区域中雷的排列有多少种。
Solution:
搜索。这题看上去1000的范围很大,实际上加上合理的剪枝,状态数会变得非常非常少。
一个雷最多能影响3个格子,直接从上往下枚举这个地方有没有雷。有雷的话给影响的格子的数字减一。
出现负数,或枚举到第k个位置了,第k-2个位置的数不为0的时候都是可以退出的。
这样的搜索策略使得我们几乎不会做无用功,最多向下一层就回到了正确的方向。
实际上代码也只用了15ms


#include <iostream> using namespace std; int n, ans; int s[1009];void dfs ( int x ) {if ( x - 2 > 0 && s[x - 2] != 0 ) return;if ( x == n + 1 ) {if ( s[n] == 0 ) ++ans;return ;}dfs ( x + 1 );int flag = 0;for ( int i = -1; i <= 1; ++i ) {if ( ( x + i > 0 && x + i <= n ) && --s[x + i] < 0 ) flag = 1;}if ( !flag ) dfs ( x + 1 );for ( int i = -1; i <= 1; ++i ) {if ( x + i > 0 ) ++s[x - i];} } int main() {cin >> n;for ( int i = 1; i <= n; ++i ) {cin >> s[i];}dfs ( 1 );cout << ans << endl; }
然而分析复杂度的时候我发现。。。实际上如果我们确定了第一个格子有没有雷,就可以推断出下面所有的情况!
所以只需要枚举第一个格子有没有雷就行了。显然答案的范围也在[0,2]。
由此可以见上面的搜索算法的时间复杂度其实也是O(n)的。