HDU2050 折线分割平面

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

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

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

Sample Input
2
1
2
Sample Output
2
7

分析

其实这是一个比较典型的图像方面的递推，其关键点就是观察，一条线最多可以通过多少条线，然后通过之后能增加多少面。
假如现在n=2，也就是图像***有4条射线，我们添加一条射线，最多经过4条线，增加4个面，而此题n=3时，我们需要在n=2的基础上增加两条射线，会增加4+4+1个面，两个射线之间会新增一个面。
所以可以猜想，dp[i] = dp[i] + (i-1) * 2 * 2+1
(i-1) * 2是上一轮图中射线的数量
(i-1) * 2 * 2+1是新增的面数量

AC代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 1e6+100;
typedef long long ll;

int T;
ll N;
ll dp[maxn];
void init(){ //先把所有结果打个表
    dp[1] = 2;
    for(int i = 2;i<=10000;i++){
        dp[i] = dp[i-1] + (i-1)*4+1;
    }
}
int main(){
    init();
    cin>>T;
    while(T--){
        scanf("%lld",&N);
        printf("%lld\n",dp[N]);
    }

    return 0;
}