HDU-2050 折线分割平面(递推)

Description

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

Input

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

Output

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

Sample Input

2
1
2

Sample Output

2
7

---

假设前n-1个折线已经构成最优解，第n条折线的策略是每条线都和前n-1条折线的两条边相交，则肯定会构成2 * (2*(n-1) - 1)条线段，和多出来的一个尖角构成的区域，以及两条射线分割出来的区域，所以是： $$ a_n = a_{n - 1} + 4(n - 1) - 2 + 1 + 2 = 4n-3\ \therefore a_n = 2n^2 - n + 1\ $$

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>

using namespace std;

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int caseNum; cin >> caseNum;
    while (caseNum--) {
        int n; cin >> n;
        cout << (2 * n * n - n + 1) << endl;
    }

    return 0;
}