基础算法题——折线分割平面（规律）

题目

测试平台
我们看到过很多直线分割平面的题目，今天的这个题目稍微有些变化，我们要求的是n条折线分割平面的最大数目。比如，一条折线可以将平面分成两部分，两条折线最多可以将平面分成7部分，具体如下所示。
Input
输入数据的第一行是一个整数C,表示测试实例的个数，然后是C 行数据，每行包含一个整数n(0<n<=10000),表示折线的数量。

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

Sample Input
2
1
2

题目中折线表明，折线由两条射线组成，折线上的转折点并不会与空间边界相交。

如何保证n条折线分割平面的为最大数目？
画的折线每一条射线必须与原先图中的每一条射线相交一次。

举例说明：
在 n = 1的条件下
原先图中并没有折线，那么就不需要画折线时，不需要考虑相交问题。

在 n = 2 条件下
原先图 n-1 中有两条射线，由于画新的折线每一条射线必须与原先图中的每一条射线相交一次。那么就需要在画新的折线时，将它们相交四次。

…

解题步骤：
①、相交点的数量 jd 与 n 的关系

jd[n] = 4 * (n-1) + jd[n-1]

②、jd[n] 与 n 条折线分割平面的最大数目的关系

dp[n] = jd[n] + n + 1

#include<stdio.h>
#define ll long long
ll jd[10010], dp[10010];
int n;

void init(){
	jd[1]=0;
	jd[2]=4;
	for(int i=3; i<=10000; i++){
		jd[i] = 4 * (i-1) + jd[i-1];
	}
	
	dp[1]=2;
	dp[2]=7;
	for(int i=3; i<=10000; i++){
		dp[i] = jd[i] + i + 1;
	}
}

int main(){
	init();
	scanf("%d", &n);
	for(int i=1; i<=n; i++){
		int x;
		scanf("%d", &x);
		printf("%lld\n", dp[x]);
	}
	
	return 0;
}

若对你有帮助，请给我一个小小的赞吧：)