[ACM_HDU_2050]折线分割平面

蓝飞 蓝飞 | 时间:2012-03-28, Wed | 5,730 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,为了将整个思路记录下来并顺道将文章开头提出的问题一并解决,因此花费了不少笔墨,若有兴趣可以看一下,虽然写的较多,但认真去看其实不难理解(最好是能在纸上实际画一画)。

如需转载请注明出处:蓝飞技术部落格

仅有一条评论 »

  1. 博客知识很好哈,请问可以交换链接吗?