HDOJ 2050 折线分割平面

题目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=2050
汗,半天没找出递推的关系,看了课件给的2种方法,都不明白。。。
结果去网上参考了别人的,似乎对于 F(n) = F(n-1) + 4(n-1) + 1 这个方法都不太明白。。。
大部分包括我都是理解的这个方法:

F(n) = 2*n*n – n + 1

解释:

首先分析直线分平面最多多少份:f(1)=2;f(2)=4;f(3)=7;f(4)=11……可知f(n)=f(n-1)+n且f(1)=2.可知f(n)=(1+n)*n/2+1;
同理,可将每个折线看成是两条直线,但是少了一半。因此每一条折线比两条直线分割的面的部分少2。因此n条折线比2n条直线分割平面形成的部分少2n。所以f(n)=(1+2*n)*2*n/2+1-2*n=2*n^2-n+1;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 // Author: Tanky Woo
// HDOJ 2050
#include <iostream>
using namespace std;
 
int main()
{
	int nCases, num;
	scanf("%d", &nCases);
	while(nCases--)
	{
		scanf("%d", &num);
		printf("%d\n", 2*num*num - num + 1);
	}
	return 0;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

发表评论

电子邮件地址不会被公开。 必填项已用*标注