Phủ ngắn nhất
Đề bài
Mô tả
Cho đoạn thẳng có độ dài , cần đặt lần lượt theo đúng thứ tự này lên một trục số vô hạn.
Đoạn thứ nhất được đặt sao cho một đầu mút của nó nằm tại điểm ; gọi đầu mút này là "điểm đầu", đầu mút còn lại là "điểm cuối" của đoạn.
Điểm đầu của mỗi đoạn tiếp theo phải trùng với điểm cuối của đoạn ngay trước nó. Cụ thể, nếu điểm cuối của đoạn trước có tọa độ và đoạn tiếp theo có độ dài , thì đoạn đó được đặt hoặc tại (khi đó điểm cuối của nó là ), hoặc tại (khi đó điểm cuối là ). Riêng đoạn thứ nhất cũng có thể đặt tại hoặc .
Phần phủ của các đoạn là hợp của tất cả các đoạn, tức tập các điểm thuộc ít nhất một đoạn. Dễ thấy phần phủ luôn là một đoạn thẳng. Hãy tìm độ dài nhỏ nhất có thể của phần phủ khi đặt hết đoạn mà không đổi thứ tự.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên , số bộ dữ liệu.
Mỗi bộ dữ liệu gồm hai dòng:
- Dòng thứ nhất chứa số nguyên , số đoạn thẳng.
- Dòng thứ hai chứa số nguyên , độ dài các đoạn theo thứ tự đặt.
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra trên một dòng độ dài nhỏ nhất có thể của phần phủ.
Ràng buộc
- Tổng trên tất cả các bộ dữ liệu không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 2 1 3 3 1 2 3 4 6 2 3 9 4 6 8 4 5 7 1 2 4 6 7 7 3 8 8 6 5 1 2 2 3 6 |
3 3 9 9 7 8 |
Bộ thứ ba: đặt , đoạn cuối phủ tất cả các đoạn trước, độ dài phủ là . Bộ thứ tư: đặt , phần phủ là có độ dài . |
| 1 1 1 |
1 | Chỉ có một đoạn độ dài . |
Bình luận