C++ 金字塔练习题 输出金字塔个数

Question

题目说明：
学校把球按照金子塔的形状进行存放，观察金字塔的一面，三角形最底下一层球的个数为n，那上一层的球的个数为n-1，直到顶点的球的个数即为1。
也就是说n=3时
X
X X
X X X
会有6个球。
总体来说，每个这种三角形结构只能存放1，3，6，10，15，21..个球，那么每个金字塔结构只能存放1，4，10，20，35，56，84等个球。

输入：整数T （1<=T<=20）作为测试的次数。m为球的个数（1<=m<=3*10^5）
输出：对于每个测试用例，在单独的一行上输出所需金字塔的最小数量。
实例如图所示：

Answer 1

#include <iostream>

using namespace std;


int main()
{
    int a[120];
    int b[120];
    int* opt=(int*)malloc(sizeof(int)*300001);
    opt[0] = 0;
    a[1] = 1;
    b[1] = 1;
    int c;
    for (int i = 2; i <= 120; i++)
    {
        b[i] = (i) * (i +1) / 2;
        a[i] = a[i - 1] + b[i];
    }
    
    for (int i = 1; i <300001; i++)
    {
        opt[i] = 0;
        for (int j = 120; j >0; j--)
        {
            if (a[j]>i)
            {
                continue;
            }
            else
            {
                if (opt[i]==0)
                {
                    opt[i] = opt[i - a[j]] + 1;
                }
                else if (opt[i-a[j]]+1<opt[i])
                {
                    opt[i] = opt[i - a[j]] + 1;
                }
            }
        }
    }


    int n;
    cin >> n;
    int* v = new int[n];
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }
    for (int i = 0; i < n; i++)
    {
        cout << opt[v[i]] << "\n";
    }
    cin >> n;

}