高中生程式解題系統：空間切割

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。
題目連結 http://zerojudge.tw/ShowProblem?problemid=a044。

此題可用遞迴(Recursion)或是動態規畫(Dynamic Programming)方式來解，也可以用公式解：

遞迴版本程式碼：

#include <iostream>
#include <cmath>

using namespace std;

int numD( short n )
{
    if( n <= 3 )
        return pow(2.0, n);
    else
    {
        int k = n - 1;
        int c = (k * k + k + 2)/2;
        n = n -1;
        return numD(n) + c;
    }
}

int main()
{
    int n;
    int d;

    while( cin >> n )
    {
        d = numD(n);
        cout << d << endl;
    }

    return 0;
}

公式解程式碼：

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    int n;
    int d;

    while( cin >> n )
    {
        d = (n * (n * n + 5))/6 + 1;
        cout << d << endl;
    }

    return 0;
}