trang chủ / đề bài / icpc24_mb_a

Căng dây qua cọc

Đề bài

Mô tả

Cho một dãy gồm n cái cọc 1,2,…,n nằm trên một đường thẳng. Cọc thứ i nằm ở tọa độ i và có chiều cao h[i]. Ta cần căng một sợi dây nối cọc 1 với cọc n, đi qua một số cọc trung gian i[1],i[2],…,i[k] (1<i[1]<i[2]<⋯<i[k]<n), đặt i[0]=1 và i[k+1]=n. Do ràng buộc kỹ thuật, hai cọc được chọn liên tiếp phải có chiều cao cân bằng và ở gần nhau. Cụ thể, với hai cọc được chọn liên tiếp i[j] và i[j+1] (j=0,1,…,k), phải có:

  • i[j+1]−i[j]≤D;
  • |h[i[j]]−h[i[j+1]]|≤H.

Hãy chọn tập các cọc trung gian thỏa mãn các ràng buộc trên sao cho tổng chiều cao của các cọc được chọn là nhỏ nhất.

Dữ liệu vào

  • Dòng đầu tiên chứa ba số nguyên dương n, D, H (1≤n≤10000, 1≤D≤n, 1≤H≤10000).
  • Dòng thứ hai chứa n số nguyên dương h[1],h[2],…,h[n] (1≤h[i]≤10000).

Dữ liệu ra

In ra tổng chiều cao của các cọc được chọn trong phương án tối ưu, tính cả cọc 1 và cọc n. Nếu không có cách chọn nào, in ra −1.

Ràng buộc

  • 1≤n≤10000
  • 1≤D≤n
  • 1≤H≤10000
  • 1≤h[i]≤10000

Ví dụ

Input Output Giải thích
13 4 2
4 1 7 2 6 3 5 1 7 5 3 4 3
13 Chọn các cọc 1,4,8,11,13, tổng chiều cao là 4+2+1+3+3=13.
6 2 3
2 5 9 4 1 4
15 Ví dụ bổ sung, tính bằng lời giải mẫu. Chọn các cọc 1,2,4,6, tổng chiều cao là 2+5+4+4=15. Từ cọc 1 không thể đi tới cọc 3 vì |2−9|>3.

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