最基础的穷竭搜索——《挑战程序设计竞赛》

发表于 | 分类于 | 浏览次数
字数统计: 1,214 字 | 阅读时长 ≈ 5 分钟

2.1.4 深度优先搜索

[http://poj.org/problem?id=2386]: “Lake Counting”

有一个大小为N*M的园子，雨后积了很多水。八连通的积水被认为是在一起的。请求出园子里共有多少个水洼？(八连通是指下图中相对.的8 部分)
www
w.w
www

从任意的’W’开始，不停地把邻接的部分用’.’代替，一次DFS(深度优先遍历)遍历后，与初始的这个 W 所连接的所有 ‘W’ 都会被替换成 ‘.’，因此直到图中没有 ‘W’为止，总共进行 DFS 的次数即为积水的次数。
使用深度优先搜索，从任意W开始，进入DFS，在DFS中把八联通的邻接部分都’.’代替，若八连通区域中又有一个”W”，进入下一层DFS，直到当前的连通分支不再有W，总共DFS的次数就是答案。八连通对应着8个方向的状态转移，每个格子至多调用一次DFS，所以复杂度是$O(8\times N \times M) = O(N \times M)$。

2.1.6 特殊状态的枚举

C++的algorithm库中提供了next_permutation这一函数，可以把n给元素共n!种不同的排列生成出来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
using namespace std;
const int MAX_N = 100;
bool used[MAX_N];
int perm[MAX_N];

//生成{0, 1, 2, 3,..., n-1}的n!种排列 
void permutation1(int pos, int n){
	if(pos == n){
		for(int i=0;i<n;i++)
			cout<<perm[i]<<" ";
		cout<<endl;
		return;
	}
	//针对perm的index为pos的位置，究竟使用0~n-1种的哪一个进行循环 
	for(int i = 0; i< n; i++){
		if(!used[i]){
			perm[pos] = i;
			used[i] = true;
			permutation1(pos + 1, n);
			used[i] = false;
		} 
	}
	return;
}

int main()
{
	permutation1(0,5);
	return 0;
}

调用函数时，主调函数所拥有的局部变量等信息需要存储在特定的内存区域，这个区域叫做栈内存区；另一方面，利用new或者malloc进行分配的内存区域叫做堆内存。
栈内存在程序启动时被统一分配，此后不能再扩大，由于这一区域有上限，所以函数的递归深度也有上限。
显式初始化全局变量被保存在数据段种，未显式初始化的全局变量保持在BSS段中。使用全局变量可以减小栈溢出的危险。

2.2 贪心法

  1. [http://poj.org/problem?id=3617]: “Best Cow Line”

已知一段长度为N的字符串S，构造一个字典序最小的字符串T。起初T为空串，随后反复进行下列任意操作。
-从S的头部删除一个字符，加到T的尾部
-从S的尾部删除一个字符，加到T的尾部

贪心算法很容易想到：不断取S的开头和末尾中较小的一个字符放到T的末尾。如果两个字符相等，那么就不断比较下一个内部字符的大小。

  1. [http://poj.org/problem?id=3253]: “Fence Repair”

    有一位农夫要把一个木板(长度为 N 块木板长度之和)使用 (N-1) 次锯成 N 块给定长度的小木板，每次锯都要收取一定费用，这个费用就是当前锯的这个木板的长度，给定各个要求的小木板的长度，及小木板的个数 N，求最小的费用。

切割的方法可以参见如下的二叉树：

1
2
3
4
5
6
7
     15
    /  \
  7      8
 / \    / \
3   4  5   3
          / \
         1   2

一个叶子就相当于一个小木板，那么开销的合计即为：

此时最佳的切割方式为：最短的板与次短的板的节点应当是兄弟节点

不妨将$L_i$按大小顺序排列，那么最短的板$L_1$与次短的板$L_2$应当为兄弟节点，因为切割是自由的不妨当作$L_1$和$L_2$是最后切开的，那么这次切割之前就有：

这样的N-1块木板存在。之后递归第将这N-1块木板的问题求解，每次加上最短的板与次短的板的长度之和即得解。时间复杂度为$O(N^2)$。事实上最佳的复杂度为$O(NlogN)$，之后将会学到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
using namespace std;
int N;
int L[50010];

int main()
{
	cin>>N;
	for(int i=0;i<N;i++)
	{
		cin>>L[i];
	}
	long long ans = 0;
	while(N>1)
	{
		int mii1 = 0, mii2 = 1;
		if(L[mii1]>L[mii2])swap(mii1,mii2);
		for(int i=2;i<N;i++)
		{
			if(L[i]<L[mii1])
			{
				mii2 = mii1;
				mii1 = i;
			}
			else if(L[i]<L[mii2])
			{
				mii2 = i;
			}
		}
		int t = L[mii1] + L[mii2];
		ans += t;
		if(mii1==N-1)swap(mii1,mii2);
		L[mii1] = t;
		L[mii2] = L[N-1];
		N--;
	}
	cout<<ans<<endl;
	return 0;
}