Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Giải thuật] Chia đoạn tối thiểu tổng bình phương

    Cho dãy số nguyên không âm a1,…,ana_1, \dots, a_na1​,…,an​ và số nguyên kkk. Hãy chia dãy thành đúng kkk đoạn con liên tiếp không rỗng. Chi phí của một đoạn bằng bình phương tổng các phần tử trong đoạn. Tổng chi phí là tổng chi phí của kkk đoạn.

    Hãy tìm cách chia có tổng chi phí nhỏ nhất. Vì hàm chi phí thoả tính đơn điệu của điểm chia tối ưu, có thể dùng tối ưu chia để trị (divide and conquer DP) đạt O(nklog⁡n)O(nk\log n)O(nklogn).

    Ví dụ: a=[1,2,3,4]a=[1,2,3,4]a=[1,2,3,4], k=2k=2k=2: chia [1,2,3] ∣ [4][1,2,3]\,|\,[4][1,2,3]∣[4] cho chi phí 36+16=5236+16=5236+16=52; chia [1] ∣ [2,3,4][1]\,|\,[2,3,4][1]∣[2,3,4] cho 1+81=821+81=821+81=82; chia [1,2] ∣ [3,4][1,2]\,|\,[3,4][1,2]∣[3,4] cho 9+49=589+49=589+49=58. Nhỏ nhất là 525252.

    • Định dạng đầu vào:

      Dòng đầu chứa nnn và kkk. Dòng thứ hai chứa nnn số nguyên không âm.

    • Ràng buộc đầu vào:

      1≤k≤n≤40001 \le k \le n \le 40001≤k≤n≤4000, 0≤ai≤1040 \le a_i \le 10^40≤ai​≤104.

    • Định dạng đầu ra:

      In ra tổng chi phí nhỏ nhất.

    Ví dụ:

    Đầu vào:

    4 2
1 2 3 4

    Đầu ra:

    52

    Giải thích:

    Có ba cách chia thành 2 đoạn. [1,2,3]|[4] cho 6^2+4^2=52; [1,2]|[3,4] cho 3^2+7^2=58; [1]|[2,3,4] cho 1+81=82. Nhỏ nhất là 52.

    Đang tải editor...