trang chủ / đề bài / mincover

Phủ ngắn nhất

Đề bài

Mô tả

Cho n đoạn thẳng có độ dài a1,a2,…,an, 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 0; 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 độ x và đoạn tiếp theo có độ dài d, thì đoạn đó được đặt hoặc tại [x−d,x] (khi đó điểm cuối của nó là x−d), hoặc tại [x,x+d] (khi đó điểm cuối là x+d). Riêng đoạn thứ nhất cũng có thể đặt tại [−a1,0] hoặc [0,a1].

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 n đoạn mà không đổi thứ tự.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên t, 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 n, số đoạn thẳng.
  • Dòng thứ hai chứa n số nguyên a1,a2,…,an, độ 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

  • 1≤t≤1000
  • 1≤n≤104
  • 1≤ai≤1000
  • Tổng n trên tất cả các bộ dữ liệu không vượt quá 104.

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 [0,6]→[4,6]→[4,7]→[−2,7], đoạn cuối phủ tất cả các đoạn trước, độ dài phủ là 9. Bộ thứ tư: đặt [0,6]→[−2,6]→[−2,2]→[2,7], phần phủ là [−2,7] có độ dài 9.
1
1
1
1 Chỉ có một đoạn độ dài 1.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0