Lấy Số Hai Đầu · canuc80k5237 · Thuật toán Canuc80k

Có một dãy $n$ số nguyên. Hai người lần lượt lấy đúng một số ở đầu trái hoặc đầu phải của dãy còn lại và cộng số đó vào điểm của mình. Cả hai đều tối đa hóa tổng điểm cuối cùng; người thứ nhất đi trước.

Input

Dòng đầu chứa $n$ ; dòng sau chứa $n$ số nguyên.

Output

In tổng điểm lớn nhất người thứ nhất có thể bảo đảm.

Constraints

$1 \leq n \leq 5000$ .
$- 1 0^{9} \leq a_{i} \leq 1 0^{9}$ .

Scoring

Subtask $1$ ( $50%$ số điểm): các test $1$ - $10$ có kích thước nhỏ, thuận tiện kiểm chứng độc lập.
Subtask $2$ ( $50%$ số điểm): không có giới hạn bổ sung ngoài các cận đã nêu.

Example

Test 1

Input

1
1

Output

Giải thích: Dãy chỉ có số $1$ . Người thứ nhất lấy phần tử duy nhất và nhận toàn bộ giá trị $1$ , nên đáp án là $1$ .

Ý tưởng và thuật toán: Đặt D[l][r] là hiệu điểm lớn nhất người sắp đi có thể đạt so với đối thủ khi đoạn còn lại là a[l..r].
Ý tưởng và thuật toán: Lấy trái: người hiện tại nhận a[l], sau đó đối thủ có lợi thế D[l+1][r]; hiệu ròng là a[l]-D[l+1][r].
Ý tưởng và thuật toán: Lấy phải: hiệu ròng là a[r]-D[l][r-1].
Ý tưởng và thuật toán: Vì người hiện tại chọn tốt nhất:
Ý tưởng và thuật toán: D[l][r] = max(a[l]-D[l+1][r], a[r]-D[l][r-1]), với D[i][i]=a[i].
Ý tưởng và thuật toán: Nếu S là tổng cả dãy và D=D[0][n-1], hai tổng điểm P1,P2 thỏa P1+P2=S, P1-P2=D; do đó P1=(S+D)/2.
Ý tưởng và thuật toán: Code nén DP: trước khi xử lý độ dài mới, dp[l] giữ D[l][r-1], còn dp[l+1] đã giữ D[l+1][r]. Duyệt l tăng dần để hai giá trị đều còn đúng lúc dùng.
Chứng minh đúng đắn: Chứng minh quy nạp theo độ dài đoạn. Với đoạn một phần tử, người hiện tại lấy nó nên D[i][i]=a[i] đúng.
Chứng minh đúng đắn: Giả sử công thức đúng cho mọi đoạn ngắn hơn. Ở a[l..r], luật chỉ cho phép hai nước đầu. Sau khi lấy một đầu, vai trò đổi và theo giả thiết quy nạp đối thủ đạt lợi thế tối ưu trên đoạn còn lại; vì vậy lợi thế của người hiện tại đúng là giá trị lấy được trừ lợi thế đó. Chọn lớn hơn trong hai khả năng xét hết mọi nước hợp lệ và cho D[l][r] tối ưu.
Chứng minh đúng đắn: Công thức đại số từ tổng và hiệu khôi phục duy nhất điểm người đầu. Nén bộ nhớ không đổi thứ tự phụ thuộc nên không đổi giá trị DP.
Độ phức tạp: O(n^2) thời gian, O(n) bộ nhớ.