Bedao Regular Contest 05 - FACTORY

Xem dạng PDF
Gửi bài giải
Điểm: 0,50 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Ở xưởng xí nghiệp Bedao, có ~k~ người thợ và có ~n~ tấm bảng cần tô được đặt cạnh nhau, tấm bảng thứ ~i~ tô tốn mất ~a_i~ đơn vị thời gian. Tại một thời điểm, mỗi người thợ chỉ được tô một tấm bảng.

Để hoàn thành công việc này trong thời gian nhanh nhất có thể, ~k~ người thợ đã thống nhất chia ~n~ tấm bảng thành ~k~ phần phân biệt, mỗi phần gồm một hoặc một số tấm bảng bất kì trong ~n~ tấm bảng.

Dưới vai trò là một chủ xưởng xí nghiệp, bạn cần phải chia ~n~ tấm bảng thành ~k~ phần sao cho thời gian hoàn thành công việc là sớm nhất.

Input

  • Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ ~( 1 \leq k \leq n \leq 12 )~
  • ~n~ dòng tiếp theo là các số ~a_i~ là thời gian để tô tấm bảng thứ ~i~ ( ~1 \leq a_i \leq 10^3~ )

Output

  • Một số nguyên là thời gian sớm nhất để hoàn thành công việc yêu cầu

Sample Input

4 3
1 
5 
3 
5

Sample Output

5

Note

Ta có thể chia ~4~ tấm bảng thành ~3~ phần như sau: ~{[1,3],[5],[5]}~ và có thời gian hoàn thành công việc là ~5~, cũng là thời gian hoàn thành sớm nhất

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 0
    nakiri_ayame  đã bình luận lúc 31, Tháng 3, 2026, 13:31

    Mình xin được đề xuất một cách giải khác so với cách chặt nhị phân:

    Đặt trạng thái dp là ~dp[i][mask]~ là thời gian hoàn thành nhỏ nhất sau khi phân chia các tấm bảng tương ứng với ~mask~ cho ~i~ người công nhân đầu tiên.

    Chuyển trạng thái: $$dp[i][mask] = \min_{submask \subset mask} \{ \max(dp[i-1][mask \setminus submask], \text{sum}(submask)) \}$$ Với submask là tập con của mask, sum(submask) là tổng thời gian hoàn thành các tấm bảng trong tập submask.

    Đáp án sẽ là ~dp[k][(1 << n) - 1]~.

    Code của mình


  • -10
    VVUU  đã bình luận lúc 11, Tháng 3, 2024, 7:12

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.