写题记录

今天这题取自于今天的牛客周赛D题，

#include 
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 5;
ll dp[MAXN][4];
void solution() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        ll a[MAXN];
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        for (int i = 0; i <= n; i++) {
            for (int k = 0; k < 4; k++) {
                dp[i][k] = -1e18; 
            }
        }
        dp[0][0] = 0; 
        for (int i = 1; i <= n; i++) {
            for (int k = 0; k < 4; k++) {
                if (dp[i - 1][k] != -1e18) {
                    dp[i][k] = max(dp[i][k], dp[i - 1][k] + a[i]);
                }
            }
            if (i >= 2) {
                for (int k = 0; k < 4; k++) {
                    if (dp[i - 2][k] != -1e18) {
                        dp[i][k] = max(dp[i][k], dp[i - 2][k]);
                    }
                }
            }
            if (i >= 3) {
                for (int k = 0; k < 4; k++) {
                    if (dp[i - 3][k] != -1e18) {
                        dp[i][k] = max(dp[i][k], dp[i - 3][k]);
                    }
                }
            }
        }
        ll ans = -1e18;
        for (int k = 0; k < 4; k++) {
            ans = max(ans, dp[n][k]);
        }
        cout << ans << endl;
    }
}

int main() {
    solution();
    return 0;
}

测试点都能过，再见咯，敬请期待下次更新！！