Người Gửi: Darkness
- Problem:
Cho dãy số gồm có N phần tử. Dãy số A được gọi là đối xứng nếu như A[i] = A[N-i+1] với mọi giá trị i từ 1 đến N.
Bạn được phép sử dụng thao tác gộp số, tức loại bỏ đi 2 số liền nhau trong dãy số và thay thế chúng bằng một số mới có giá trị bằng tổng của 2 số đã chọn.
Với một dãy số cho trước, hãy tính số thao tác sử dụng ít nhất để có thể biến đổi dãy số ban đầu thành một dãy số đối xứng?
Input
Dòng đầu tiên là N (N ≤ 106), số lượng phần tử trong dãy số ban đầu.
Dòng tiếp theo gồm N số nguyên A[i] (1 ≤ A[i] ≤ 109).
Output
In ra một số nguyên là đáp án của bài toán.
Example:
Input
3
1 2 3
Output:
1
Input
4
1 4 3 2
Output:
2
- Solution:
Input
4
1 4 3 2
Output:
2
Giải thích test 1: 1 2 3 là 3 3
Giải thích test 2: 1 4 3 2 là 5 3 2 là 5 5
Tư tưởng của bài này là bạn cần hai biến chạy:
- i: chạy từ đầu về cuối.
- j: chạy từ cuối về đầu.
[i]==[j]: chạy tiếp;
[i]<[j]: cộng dồn [j] với [j-1] và j chạy tiếp;
[i]>[j]: cộng dồn [i] với [i+1] và i chạy tiếp;