[ACM_HDU_2050]折线分割平面

杰拉斯 | 时间：2012-03-28, Wed | 7,392 views
编程算法　

折线分割平面

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 8663 Accepted Submission(s): 6084

Description

我们看到过很多直线分割平面的题目，今天的这个题目稍微有些变化，我们要求的是n条折线分割平面的最大数目。比如，一条折线可以将平面分成两部分，两条折线最多可以将平面分成7部分，具体如下所示。

Input

输入数据的第一行是一个整数C,表示测试实例的个数，然后是C 行数据，每行包含一个整数n(0<n<=10000),表示折线的数量。

Output

对于每个测试实例，请输出平面的最大分割数，每个实例的输出占一行。

Sample Input

2
1
2

Sample Output

2
7

Source

HDU2050

与@王xiao瓶一同讨论了这道题，过程如下：

先思考这么一道题：

在一个平面上有一个圆和n条直线，这些直线中每一条在圆内同其他直线相交，假设没有3条直线相交于一点，试问这些直线将圆分成多少区域。

很容易看出递推关系，每新增一条直线，都将原来所有的区域分成两半，因此第n条直线会在原来的基础上再添加n个平面，函数递推关系式如下：

递推公式1：

f(0) = 1
f(1) = 2
f(2) = 4
...
f(n) = f(n - 1) + n

通项公式推导1：

f(n)
= f(n - 1) + n
= f(n - 2) + n + (n - 1)
= ...
= f(0) + n + (n - 1) + ... + 1
= 1 + (1 + n) * n / 2

我们再深入讨论，若每次使用两条直线分割，即此时的n相当于原来的2n，可得：
递推公式2：

f(0) = 1
f(1) = 4
f(2) = 11
...
f(n) = f(n - 1) + 2 * n - 1 + 2 * n = f(n - 1) + 4 * n - 1

通项公式推导2_1：

f(n)
= f(n - 1) + (4 * n - 1)
= f(n - 2) + 4 * (n - 1) - 1 + (4 * n - 1)
= ...
= f(0) + (4 * 1 - 1) + (4 * 2 - 1) + ... + (4 * n - 1)
= 1 + 4 * (1 + 2 + .. + n) - n
= 1 + 4 * (1 + n) * n / 2 - n
= 1 + 2 * n * n + n

上面的推导公式比较复杂，其实也可以直接将通项公式推导1中推导结果的n用2n替代，这样就容易理解多了：
通项公式推导2_2：

f(n)
= 1 + (1 + (2 * n)) * (2 * n) / 2
= 1 + 2 * n * n + n

那我们再来考虑折线的情况，若是普通直线，相交处所分割的平面为4份，而折线为两份，即每次分割比上面所考虑的情况少2份，那么只要在上述情况的每次分割时减去2就能得到本题的结果了。

递推公式3：

f(n)
= f(n - 1) + 4 * n - 1 - 2
= f(n - 1) + 4 * n - 3

通项公式：

f(n)
= 1 + 2 * n * n + n - 2 * n
= 1 + 2 * n * n - n

递推解决方案：

int main()
{
	int i, n, a[10001];
	a[1] = 2;
	for(i = 2; i < 10001; ++i){
		a[i] = a[i - 1] + 4 * i - 3;
	}
	cin >> n;
	while(n--){
		cin >> i;
		cout << a[i] << endl;
	}
	return 0;
}

通项公式解决方案：

int main()
{
	int n, i;
	cin >> n;
	while(n--){
		cin >> i;
		cout << 2 * i * i - i + 1 << endl;
	}
	return 0;
}

两种都可以Accept但显然第二种方法既省时间，又省空间。算法其实很简单，只需要一道公式便能解决，主要是能够分析出递推关系以及通项公式。其实本题并不需要这么大费周章，只是刚开始系统地学习ACM，为了将整个思路记录下来并顺道将文章开头提出的问题一并解决，因此花费了不少笔墨，若有兴趣可以看一下，虽然写的较多，但认真去看其实不难理解（最好是能在纸上实际画一画）。

如需转载请注明出处：杰拉斯的博客

杰拉斯的博客