【NEUQACM OJ】1017: 平面切割（特别版）

题目描述

我们要求的是n条闪电型折线分割平面的最大数目。比如，一条闪电型折线可以将平面分成两部分，两条最多可以将平面分成12部分，三条最多可将平面分成31部分，四条最多则可将一个平面分为59部分。

输入

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

输出

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

样例输入

　　　　　 1　　2　　3

样例输出

提示

注意用递归的方式找到数学公式哦~

一致的数据比较多，而且题目提示用递归数学公式，也就是数学上的递推公式；

我们来分析下，已知的几组数组

闪电星折线为 n=1 时平面被分成C=2 份

n=2 C=12 情况

有前两组数据，及几何图形，可推知，n每增加1，C的增加跟n正相关，即每次C的增加数量是在前一次C值的基础上增加特定的值，即前后两项无倍数关系

下面假设递推公式 C[i]=C[i-1];

下面来代入题目中给的数据

n=2;

C[2]=C[1]=2 而实际C[2]=12; 前者少1*10-0;

n=3;

C[3]=C[2]=12 而实际C[3]=31; 前者少2*10-1;

n=4;

C[4]=C[3]=31 而实际C[4]=59; 前者少3*10-2;

很容易得到正确的递推公式为C[i]=C[i-1]+10*(i-1)-(i-2);

递推公式出来了，下面贴代码：

2016-06-05-17:51:21

 #include<iostream>

 using namespace std;

 int a[];

void list()

 {

     a[]=;

     for(int i=;i<=;i++)

    {

        a[i]=a[i-]+(i-)*-(i-);

    }

 }

 int main()

 {

     int n,N;

     cin>>N;

    list();

     while(N--)

    {

         cin>>n;

        cout<<a[n]<<endl;

     }

     return ;

  }

巴特西

【NEUQACM OJ】1017: 平面切割（特别版）

最新文章

热门文章