先将整个塔变为一个直角三角形的模样。这时就可以很好的用数组表示了,这时发现答案就是一个倒着的等腰直角三角形的和(不考虑边界)。
考虑预处理。
令 \(a_i\) 为点 \(i\) 所在的行数,\(f_i\) 表示 \(i\) 号点的答案,\(g_i\) 表示 \(i\) 和 它正上方的元素的价值。
当 \(i\) 为当前行的第一个数时,显然 \(f_i = f_{i - a_i + 1} + i ^ 2\),\(g_i = g_{i - a_i + 1} + i ^ 2\)
当 \(i\) 为当前行的最后一个数时,显然 \(f_i = f_{i - a_i} + i ^ 2\),\(g_i = i ^ 2\)
否则 \(f_i = f_{i - a_i} + g_{i - a_i + 1} + i ^ 2\),\(g_i = g_{i - a_i + 1} + i^2\)
边界:\(f_1 = g_1 = 1\)。\(g_1\) 其实可以不赋值,因为第一列是特判了的,转移时就用不到第一列的 \(g\) 了。
时间复杂度:\(\mathcal{O}(n + m)\)
代码:
const int N = 1e6 + 100;
int n;
int a[N];
ll f[N], g[N];
int main() {
ios
n = (int) (1e6);
int now = 0, cur = 0;
for (int i = 1; cur == 0; i++)
for (int j = 1; j <= i; j++) {
now++;
if (now > n) {
cur = 1;
break;
}
a[now] = i;
}
f[1] = g[1] = 1;
for (ll i = 2; i <= n; i++) {
if (a[i] != a[i - 1]) {
f[i] = f[i - a[i] + 1];
g[i] = g[i - a[i] + 1] + i * i;
}
else if (a[i] == a[i - a[i] + 1]) {
f[i] = f[i - a[i]];
g[i] = i * i;
}
else {
f[i] = f[i - a[i]] + g[i - a[i] + 1];
g[i] = g[i - a[i] + 1] + i * i;
}
f[i] += i * i;
}
int T;
cin >> T;
while (T--) {
int x;
cin >> x;
cout << f[x] << "\n";
}
return 0;
}