tuyethoa0804

Đây là bài đầu tiên mình đăng, có gì sai sót mong các bạn thông cảm nhé :)

Sự thể là, một hôm lôi chồng sách tin cũ (thời 1997), gặp ngay cái bài này, mình chẳng biết giải thế nào nữa. Bạn nào gặp rồi hay biết làm thì bày thuật toán cho mình với nhé. Bài toán như sau:

Giả sử cho dãy 3 số: 3 2 5. Chia nó làm 2 phần, chia là: (3 2) (5). Độ chênh lệch là 0

Giả sử cho dãy 3 số: 3 5 2. Chia nó làm 2 phần, chia là: (3) (5 2). Độ chênh lệch là |3 - 5| + |(5 + 2) - 5| = 4

Hãy chia một dãy Ai dài tối đa 256 phần tử có giá trị không âm và nhỏ hơn 25.000.000 thành N đoạn sao cho độ chênh lệch nhỏ nhất. 1<=N<=256. (Không được làm biến đổi thứ tự của dãy)

 | 
RR

Lúc chia thành nhiều hơn 2 đoạn thì tính độ chênh lệch như nào vậy? Tổng hay là max?

tuyethoa0804
Trả lời RR
  Hiện bài gốc

Độ chênh lệch là tổng của trị tuyệt đối các hiệu giữa độ dài Ai và A trung bình bạn à

RR
Trả lời tuyethoa0804
  Hiện bài gốc

Nếu thế thì quy hoạch động bạn à.

Nếu bạn chưa biết về quy hoạch động thì có thể đọc trong Giải thuật và lập trình hoặc Tài liệu giáo khoa chuyên tin (link)

  • Đầu tiên nhận thấy là do N cố định, nên bạn có thể tính được A trung bình, đặt là A0 đi.
  • Giờ gọi f(i, k) = độ chênh lệch nhỏ nhất nếu chia các số A1, A2, ..., Ai vào k nhóm.
    • Để tính f(i, k) thì bạn xét cái đoạn thứ k gồm những số nào.
    • Nếu đoạn thứ k gồm các số Aj, A(j+1), ..., A(i) thì: f(i, k) = f(j-1, k-1) + | Aj + ... + Ai | - A0
    • Do đó để tính f(i, k) thì bạn for tất cả các j rồi lấy min theo công thức trên.

© VNOI Team 2015