解题思路

观察数列 1、2、9、33、126、477，找到规律：从第 3 项起，每一项等于前两项之和的 3 倍，即 a_i = 3 × (a_{i-1} + a_{i-2})。

用递推算出第 N 项，同时累加得到前 N 项和。N 最大 17，数增长较快，用 long long。

参考代码

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long a[20];
    a[1] = 1; a[2] = 2;
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        if (i >= 3) a[i] = 3 * (a[i - 1] + a[i - 2]);
        sum += a[i];
    }
    cout << a[n] << endl;   // 第N项
    cout << sum << endl;    // 前N项和
    return 0;
}

复杂度分析

循环 n 次，n 最大 17，时间复杂度 O(n)，额外空间复杂度 O(n)。