思路
我们实际上发现它计算的就是 \(p_i \cdot i\) 的和再减去一个 \(p_i \cdot i\) 中的最大值。
那我们可以枚举这个最大值 \(p_x \cdot x\)，这个值就是最后和中需要删除的数值。
这里我们可以使用贪心。
我们可以从 \(n \sim 1\) 枚举除 \(p_i\) 的每个数字需要配的数字。
当然，越大的数字 \(p_i\)，配的数字 \(i\) 也应该越大，这样才能使和最大。
我们还要注意选最大的 \(p_i \cdot i\) 一定不能超过 \(p_x \cdot x\)。
加一些剪枝就过了。
最坏时间复杂度：\(O(n^4)\)，最多需要跑 \(4.6 \times 10^9\) 次。
因为时间限制有 \(3\) 秒（不要质疑 CF 的机子），所以放心跑。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 260;
bool vis[N];
void solve() {
int n, ans = 0;
cin >> n;
int res = 0;
for (int a = 1; a <= n; a++) {
for (int b = 1; b <= n; b++) {
int maxx = a * b, ans = 0;
if (maxx < n) continue;
if (a * b * n <= res) continue;
memset(vis, 0, sizeof(int) * (n + 10));
vis[b] = true;
for (int i = n; i >= 1; i--) {
if (i == a) continue;
int maxp = min(n, maxx / i);
while (maxp >= 1 && vis[maxp]) maxp--;
if (maxp == 0) {
ans = -0x3f3f3f3f;
break;
}
vis[maxp] = true;
ans += maxp * i;
}
// cout << a << ' ' << b << ' ' << ans << endl;
res = max(res, ans);
}
}
cout << res << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) solve();
return 0;
}