Free Contest 111 - CALPLUS

Xem dạng PDF

Gửi bài giải

Điểm: 1,37 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M

Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Lưu ý: các bạn không nhập, xuất dữ liệu bằng file kể cả khi đề bài có yêu cầu. Đọc, ghi dữ liệu được thực hiện ở stdin và stdout.


Bình luận

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



  • 4
    giabao8a70409042008  đã bình luận lúc 29, Tháng 7, 2023, 2:40

    Cho mình xin phép chia sẻ lời giải để các bạn chưa làm được có thể tham khảo ạ.

    Gọi ~dp[i][j]~ là thời gian ít nhất để máy tính của An tính được tổng các phần tử trong đoạn ~[i..j]~

    Ta có ~dp[i][i] = 0~

    Xét ~dp[i][j]~ với ~j > i~

    Để tính được tổng từ đoạn ~[i..j]~ thì ta chia đoạn đó thành 2 đoạn ~[i..k]~ và ~[k + 1..j]~ (với ~i ≤ k < j~)

    Sau đó khi gộp 2 đoạn nhỏ lại thì tốn thêm chi phí là ~(a[i] + a[i + 1] + ... + a[j])^2~

    Khi đó ~dp[i][j] = min(dp[i][k] + dp[k + 1][j] + (a[i] + a[i + 1] + ... + a[j])^2)~

    Đáp án là ~dp[1][n]~. ĐPT là ~O(n^3)~

    Để AC thì ta cần tối ưu QHĐ bằng kỹ thuật Knuth Optimization:

    Gọi ~opt[i][j]~ là vị trí k thỏa mãn ~dp[i][j] nhỏ nhất

    Có thể chứng minh rằng ~opt[i][j-1] ≤ opt[i][j] ≤ opt[i+1][j]~ (Xem thêm phần chứng minh và Knuth Optimization tại đây)

    Vậy để tính ~opt[i][j]~ thì ta chỉ cần duyệt từ ~opt[i][j-1]~ đến ~opt[i+1][j]~. Thao tác này mất ~O(1)~.

    Code của mình để tham khảo (đã AC)

    Chúc các bạn một ngày vui vẻ! <3


    • 1
      Winboy423minhkhoi  đã bình luận lúc 29, Tháng 7, 2023, 12:17

      =)) cho sol đc rồi, không cần gửi code đâu ( sợ coder khác ỷ lại )


  • -1
    madv809  đã bình luận lúc 5, Tháng 12, 2021, 13:45

    Đề bài này có vẻ khi lấy từ Freecontest có bị thiếu dữ kiện, các bạn đợi admin sửa lại trước khi làm nhé, không thì ngồi nghĩ sml như mình:v


    • 8
      VPhgK39  đã bình luận lúc 6, Tháng 1, 2022, 14:15

      Bài này hình như phải là x và y là 2 số liên tiếp :3