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

    solution

    Đề bài: [Giải thuật] Nhân chuỗi ma trận tối ưu

    Cho nnn ma trận A1,…,AnA_1,\dots,A_nA1​,…,An​ trong đó AiA_iAi​ có kích thước pi−1×pip_{i-1} \times p_ipi−1​×pi​. Tìm số phép nhân vô hướng nhỏ nhất để tính tích A1A2⋯AnA_1 A_2 \cdots A_nA1​A2​⋯An​ bằng cách đặt dấu ngoặc tối ưu.

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

      Dòng đầu: nnn. Dòng hai: n+1n+1n+1 số p0,p1,…,pnp_0, p_1, \dots, p_np0​,p1​,…,pn​.

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

      1≤n≤5001 \le n \le 5001≤n≤500, 1≤pi≤10001 \le p_i \le 10001≤pi​≤1000.

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

      Một số nguyên: số phép nhân vô hướng nhỏ nhất.

    Ví dụ:

    Đầu vào:

    3
10 20 30 40

    Đầu ra:

    18000

    Giải thích:

    (A1A2)A3: 10*20*30 + 10*30*40 = 6000+12000=18000; A1(A2A3): 20*30*40+10*20*40=24000+8000=32000. Tối ưu 18000.

    Đang tải editor...