AOJ 784.平面分隔问题

189

题目



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;
}
发布评论
  • 点击查看/关闭被识别为广告的评论