HDU-2050

首先，对于这种输入和输出均只有一个数的，那么首先需要想到的就是数列。
那么，问题就是输入n，如何求数列的第n项。
这个从高中的知识就可以得到，要么找递推公式，要么找通项公式。
不过事实上找通项公式的难度一般远大于找递推的，所以我们遇到这种问题首先想的就是找递推公式。
递推公式的话，那么其基本思想就是从前面的一个状态推到当前的状态。
好的，于是问题就变成，现在给出有n条折线的最优划分方案，问再加一条的话最优划分方案是多少。
在此之前我们先规定在平面内永远都不要做两条平行的线，这个显然可以做到。
首先考虑在有两条折线的时候的情况：

image
那么这里面有几个区域就很好数了，一共是7个。
那么第三条折线怎么画是最优的呢？在这之前我把问题转化为做两条起点相同的射线。
首先我们知道所有的线都两两不平行。也就是说我可以做一条跟他们都不平行的线来跟他们都相交。
那么在这个图里，就有4条线，于是我们先做第一条射线。我们的目标是令其跟已知的所有线都相交。于是就可以这么做：
image
这条射线经过了4条线，一共被分为5小段，除了最靠近射线起点的那一段之外剩下的每一段都割开了一个区域。
那么同理的，我也可以从同个起点出发，再做一条与4条线相交的射线：
image.png
那么类似的，我同样得到了5个线段，除了最靠近射线起点的那一段之外剩下的每一段都割开了一个区域。
还有就是，靠近射线起点的两条线段组成一个小折线，又可以割出一块。
好了，于是我们就可以知道，做第三条折线一共可以割出4+4+1块。
接着我们把情况推到n条折线。当然前面的假设还是成立的，就是两两不平行的情况。
那么显然的，我可以做一条射线使其跟所有的2n条线相交，并割出2n个区域；然后再在这条射线的起点上再做一条射线，再割2n个区域，最后射线的起点端的两个小线段围住一块区域，再得到一个区域。
于是我们就可以得到这样一个结论。n+1条折线分割的区域会比n条折线分割的区域多4n+1个
那么我们假设答案是f(n)的话，那么递推式就是：f(n+1)=f(n)+4n+1
代码如下：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

LL ans[10005];

void init()
{
    ans[1]=2;
    for(int i=1;i<=10000;i++)
    {
        ans[i+1]=ans[i]+4*i+1;
    }
}

int main()
{
    init();
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        printf("%lld\n",ans[n]);
    }
    return 0;
}