Dãy Đèn Hai Màu · canuc80k7802 · Thuật toán Canuc80k

Tô đúng $R$ trong $N$ bóng đèn màu đỏ, các bóng còn lại màu xanh, để tổng phần thưởng trên những cặp kề khác màu lớn nhất.

Dòng đầu chứa $N$ và $R$ .
Dòng thứ hai chứa $N - 1$ số $A_{i}$ , là phần thưởng giữa bóng $i$ và $i + 1$ .

Subtask $1$ ( $50%$ số điểm): dữ liệu nằm trong miền nhỏ, phù hợp với lời giải vét cạn hoặc DP trực tiếp được mô tả trong tài liệu.
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Test 1

Input

5 2
3 8 2 6

Output

Giải thích: Tô đỏ các bóng $2$ và $4$ , còn lại tô xanh. Bốn cặp kề đều khác màu nên nhận $3 + 8 + 2 + 6 = 19$ .

Mô hình: Tô đúng R trong N bóng đèn màu đỏ, các bóng còn lại màu xanh, để tổng phần thưởng trên những cặp kề khác màu lớn nhất. Đại lượng bị giới hạn về số lượng được chuyển thành một khoản phạt hoặc phần thưởng, nhờ đó bỏ được chiều đếm lớn khỏi DP hay thuật toán tối ưu cơ sở.
Thuật toán: Đổi bài toán về chọn đúng min(R,N−R) đỉnh không kề có trọng số là tổng hai cạnh kề; dùng Alien Trick trên DP independent set của đường.
Chứng minh đúng: Đổi tên hai màu cho thấy chỉ cần r=min(R,N−R). Một cấu hình màu tương ứng với việc chọn r vị trí độc lập trên đường sau phép biến đổi chuẩn; trọng số vị trí i là A_{i−1}+A_i. DP independent set fixed-lambda xét bỏ i hoặc lấy i sau i−2, đồng thời đếm số vị trí. Đường bao theo số lượng là lõm, số lượng giảm khi lambda tăng, nên nghiệm tại ngưỡng cộng lại lambda*r cho đúng giá trị cần tìm.
Độ phức tạp: Mỗi lần DP O(N), tổng O(N log V) thời gian và O(N) bộ nhớ.