DCEPC501.cpp

#include <iostream>
using namespace std;

const int MAX = 1000010;

int N;                      // Số đồ chơi
int Price[MAX];             // Giá của các đồ chơi
long long MaxMoney[MAX];    // MaxMoney[i] là số tiền lớn nhất
                            // khi Leonard chọn từ đồ chơi thứ i.
int main(int argc, char** argv)
{
	int T, test_case;
	ios::sync_with_stdio(false);
	//freopen("input.txt", "r", stdin);

	cin >> T;
	for(test_case = 0; test_case  < T; test_case++)
	{
		// Nhập đầu vào
		cin >> N;
		for(int i = 1; i <= N; i++)
		{
			cin >> Price[i];
			MaxMoney[i] = 0;
		}

		// Trường hợp cơ sở
		MaxMoney[N] = Price[N];
		for(int i = N + 1; i <= N + 5; i++)
			Price[i] = MaxMoney[i] = 0;

		for(int i = N-1; i >= 1; i--)
		{
			// Nếu chọn 1 đồ chơi
			MaxMoney[i] = (long long)Price[i] + MaxMoney[i + 2];

			// Nếu chọn 2 đồ chơi
			long long t = (long long)(Price[i] + Price[i + 1]) + MaxMoney[i + 4];
			if(t > MaxMoney[i]) MaxMoney[i] = t;

			// Nếu chọn 3 đồ chơi
			t = (long long)(Price[i] + Price[i + 1] + Price[i + 2]) +  MaxMoney[i + 6];
			if(t > MaxMoney[i]) MaxMoney[i] = t;
		}
		cout << MaxMoney[1] << endl;
	}
	return 0;//Your program should return 0 on normal termination.
}