题目

Description

在平面上画n条封闭的曲线，各曲线之间两两相交于两点，并且三条封闭的曲线都不相交于一点，求这样的n条曲线将平面分为多少个区域。

Input

输入包括多组数据，每组数据占一行，且只有一个整数n(0<=n<=1000)，当n=0时表示输入结束。

Output

对每组测试数据输出一行结果，结果为一个整数，表示这n条曲线将平面划分成的区域数。

Sample Input

1
3
0

Sample Output

2
8

题解

根据数学关系得出:
a[n] = a[n - 1] + 2*(n - 1)

记忆化搜索然后计算即可

代码

/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com
 
かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
using namespace std;
 
const int maxn = 1005;
 
int Dp[maxn];
int dp(int n) {
    return Dp[n] = Dp[n]?Dp[n]:dp(n - 1) + 2*(n - 1);
}
 
bool  Do() {
    int n;
    scanf("%d",&n);
    if(n==0)
        return false;
 
    printf("%d\n",dp(n));
 
    return true;
}
 
int main() {
    Dp[1] = 2;
    while(Do());
    return 0;
}