Hải vừa được trúng thưởng cực lớn trong một trò chơi. Ban tổ chức đã chuẩn bị sẵn cho Hải n món quà có giá trị lần lượt là a0, a1, ..., an-1.

Ban tổ chức cho phép Hải chọn quà theo luật như sau:

• Mỗi lượt chỉ được chọn 1 món quà.
• Nếu lượt này đã chọn món quà thứ k thì lượt sau chỉ được chọn các phần quà từ k + 1 đến n - 1.
• Ở lượt chọn quà lẻ (lượt 1, lượt 3,...) thì Hải được chọn bất kỳ phần quà giá trị tùy ý.
• Ở lượt chọn quà chẵn (lượt 2, lượt 4,..) thì Hải bắt buộc phải chọn phần quà có cùng giá trị với phần quà ngay trước đó mà Hải đã chọn.

Hãy tìm và in ra tổng giá trị lớn nhất của các phần quà mà Hải có thể chọn.

Ví dụ:

• Test mẫu 1:
   

  Input	Output
  3 2 3 2	4

  
  Với a = [2, 3, 2], thì chooseGifts(a) = 4.
  Giải thích:
  • Lượt 1 Hải chọn phần quà có giá trị a[0] = 2, lượt 2 Hải chọn phần quà có giá trị a[2] = 2.
     
• Test mẫu 2:
   

  Input	Output
  5 10 6 7 6 1	13

  
  Với a = [10, 6, 7, 6, 1], thì chooseGifts(a) = 13.

Hướng dẫn bài tập.

Sử dụng giải thuật quy hoạch động.

Gợi ý: Dùng dãy s[n][2] để lưu tổng lớn nhất:

• s[i][0]: Tổng lớn nhất với lượt chọn lẻ kết thúc tại i.
• s[i][1]: Tổng lớn nhất với lượt chọn chẵn kết thúc tại i.

Code mẫu:

Ngôn ngữ C++:

#include<iostream>

using namespace std;

int s[10001][2];
int a[10001];
int chooseGifts(int a[], int n)
{
    for (int i = 0; i < n; i++){
		s[i][0] = a[i];
		s[i][1] = -1;
	}
	for (int i = 1; i < n; i++){
		for (int j = 0; j < i; j++)
		if (a[j] == a[i] && s[j][0] + a[i] > s[i][1])
		s[i][1] = s[j][0] + a[i];
		for (int j = 0; j < i; j++)
		if (s[j][1] + a[i] > s[i][0])
		s[i][0] = s[j][1] + a[i];
	}
	int max = -1;
	for (int i = 0; i < n; i++)
	for (int j = 0; j < 2; j++)
	if (s[i][j] > max) max = s[i][j];
    return max;
}

int main(){
	int n, x;
	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> a[i];
	}
	cout << chooseGifts(a, n);
	return 0;
}