Bedao Regular Contest 05 - FACTORY

View as PDF
Submit solution
Points: 0.42 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Problem type
Allowed languages
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

Comments

Please read the guidelines before commenting.


  • 0
    nakiri_ayame  commented on March 31, 2026, 1:31 p.m.

    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  commented on March 11, 2024, 7:12 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.