POJ 3086 Triangular Sums：三角數加權和預計算

POJ 3086 Triangular Sums：三角數加權和

第 n 個三角數 T(n) = 1+2+...+n。定義 W(n) = Σ_{k=1..n} k * T(k+1)。多組查詢，n ≤ 300，預計算後 O(1) 回答。

解題思路

預計算陣列：
T[1] = 1; for i=2..300: T[i] = T[i-1] + i;
f[i] = i * T[i+1];
sum[1] = f[1]; for i=2..300: sum[i] = sum[i-1] + f[i];
輸出編號、n、sum[n]。注意輸入格式：第一行測試用例數，後每行一個 n。

代碼實現

#include <iostream>
#include <cstdio>
using namespace std;
int f[305], T[305], sum[305];
int main() {
    T[1] = 1; f[1] = 1;
    for (int i = 2; i < 305; i++) T[i] = i + T[i-1];
    for (int i = 1; i < 304; i++) f[i] = i * T[i+1];
    sum[1] = f[1];
    for (int i = 2; i < 305; i++) sum[i] = sum[i-1] + f[i];
    int n, m;
    while (scanf("%d", &n) != EOF && n) {
        for (int i = 1; i <= n; i++) {
            scanf("%d", &m);
            printf("%d %d %d\n", i, m, sum[m]);
        }
    }
    return 0;
}

簡單高效，預處理 O(N)，查詢 O(1)。