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

    solution

    Đề bài: [Giải thuật] Quy hoạch động đường bao lồi (CHT cơ bản)

    Cho hai dãy số nguyên a0,…,an−1a_0,\dots,a_{n-1}a0​,…,an−1​ và b0,…,bn−1b_0,\dots,b_{n-1}b0​,…,bn−1​. Định nghĩa hàm quy hoạch động:

    dp0=0,dpi=min⁡0≤j<i(dpj+aj⋅bi) (1≤i≤n−1).dp_0 = 0,\quad dp_i = \min_{0 \le j < i}\left(dp_j + a_j \cdot b_i\right)\ (1 \le i \le n-1).dp0​=0,dpi​=min0≤j<i​(dpj​+aj​⋅bi​) (1≤i≤n−1).

    Hãy in giá trị dpn−1dp_{n-1}dpn−1​. (Đây là dạng quy hoạch động bao lồi; với ràng buộc cho phép có thể giải trực tiếp.)

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

      Dòng đầu: nnn. Dòng hai: nnn số aja_jaj​. Dòng ba: nnn số bib_ibi​.

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

      1≤n≤30001 \le n \le 30001≤n≤3000, −106≤aj,bi≤106-10^6 \le a_j, b_i \le 10^6−106≤aj​,bi​≤106.

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

      Một số nguyên: giá trị dpn−1dp_{n-1}dpn−1​.

    Ví dụ:

    Đầu vào:

    4
5 3 2 0
0 1 2 3

    Đầu ra:

    14

    Giải thích:

    dp0=0; dp1=0+5*1=5; dp2=min(0+5*2,5+3*2)=10; dp3=min(0+5*3,5+3*3,10+2*3)=14.

    Đang tải editor...