Atcoder Educational DP Contest N - Slimes

Points: 0.40 (partial)

Time limit: 2.0s

Memory limit: 1G

Input: stdin

Output: stdout

Suggester:

toha

Problem source:

Atcoder Educational DP Contest

Problem type

Allowed languages

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Có ~N~ cục thạch xếp thành một hàng ngang. Ban đầu, cục thạch thứ ~i~, đếm từ trái sang, có kích thước ~a_i~.

Taro cố gắng ghép những cục thạch này lại với nhau để tạo thành một cục thạch lớn hơn. Anh ấy sẽ liên tục lặp lại thao tác sau cho đến khi chỉ còn lại một cục thạch duy nhất:

Taro chọn hai cục thạch kế bên nhau và ghép chúng lại. Cục thạch mới sẽ có kích thước là ~x+y~, ~x~ và ~y~ là kích thước của hai cục thạch được chọn trước khi được ghép. Chi phí phát sinh là ~x+y~ và vị trí tương đối giữa các cục thạch là không thay đổi trong suốt quá trình kết hợp các cục thạch.

Taro là một người tiết kiệm. Bạn hãy giúp Taro tìm chi phí phát sinh nhỏ nhất có thể.

Input

Dòng đầu tiên chứa số nguyên ~N(2 \leq N \leq 400)~ là số lượng cục thạch.

Dòng thứ hai chứ ~N~ số nguyên ~a_1,a_2,a_3,...,a_n (1 \leq a_i \leq 10^9)~.

Output

Dòng duy nhất là chi phí phát sinh nhỏ nhất.

Sample 1

Input

4
10 20 30 40

Output

Taro nên thực hiện như sau (những cục thạch được ghép sẽ được in đậm).

(10, 20, 30, 40) → (30, 30, 40)
(30, 30, 40) → (60, 40)
(60, 40) → (100)

Sample 2

Input

5
10 10 10 10 10

Output

Taro có thể thực hiện các thao tác như dưới đây:

(10, 10, 10, 10, 10) → (20, 10, 10, 10)
(20, 10, 10, 10) → (20, 20, 10)
(20, 20, 10) → (20, 30)
(20, 30) → (50)

Sample 3

Input

3
1000000000 1000000000 1000000000

Output

5000000000

Câu trả lời có thể không vừa kiểu int.

Sample 4

Input

6
7 6 8 6 1 1

Output

Taro nên thực hiện các thao tác như sau:

(7, 6, 8, 6,1, 1) → (7, 6, 8, 6, 2)
(7, 6, 8, 6, 2) → (7, 6, 8, 8)
(7, 6, 8, 8) → (13, 8, 8)
(13, 8, 8) → (13, 16)
(13, 16) → (29)

Comments

Please read the guidelines before commenting.

0

2004_TranNgoNamCuong commented on Aug. 15, 2024, 3:33 a.m.

.

để giải được một bài toán quy hoạch động thì có một số bước cơ bản b1: định nghĩa bài toán con nhỏ nhất b2: giải bài toán con cơ sở b3: xác định công thức truy hồi, đáp án bài toán

- Tóm tắt đề bài:
cho một dãy gồm n số nguyên a1, a2,.. an
bạn phải cố gắng ghép 2 số nguyên liên tiếp để ghép thành một số lớn hơn và bạn phải lặp đi lặp
lại thao tác này đến khi dãy chỉ còn duy nhất một số nguyên
và mỗi khi bạn ghép hai số lại với nhau thì chi phí bạn mất sẽ là tổng của hai số bạn ghép
ví du:
dãy số ban đầu: 10, 20, 30, 40 
ta có một cách ghép ngẫu nhiên như sau:
- chọn số đầu tiên và số thứ 2 để ghép => dãy số sau khi ghép lần 1 : 30, 30, 40 => tổng chi phí mất là 0 + 30 = 30
- chọn số đầu tiên và số thứ 2 => dãy số sau khi ghép lần 2 : 60, 40 => tổng chi phí mất là 30 + 60 = 90;
- chọn hai số còn lại trong dãy => dãy số sau khi ghép lần 3 : 100 => tổng chi phí m ất là 90 + 100 = 190

**Phân tích :
b1, b2: Định nghĩa, giải bài toán con nhỏ nhất:
    nếu bạn có một dãy số gồm 1 phần tử vậy thì tổng chi phí bạn mất sẽ là giá trị của phần tử đó
    nếu bạn có một dãy số gồm 2 phần tử vậy thì tổng chi phí bạn mất sẽ là tổng giá trị của 2 phần tử đó
    vậy nếu bạn có 3 phần tử thì sao : a1, a2, a3
    cách 1 : bạn sẽ ghép a1 và a2 sau đó ghép tiếp với a3
    cách 2 : bạn sẽ ghép a2 và a3 sau đó ghép tiếp với a1
    => cách tư duy đơn giản nhất đó là lấy min của cả hai cách
    vậy nếu bạn có 4 phần tử : a1, a2, a3, a4
    có thể thấy rằng đến 4 phần tử là đã có khá nhiều cách khác nhau để tính
    bạn có thể:
    - ghép a1 với a2, sau đó ghép với a3 rồi a4
    - ghép a1 với a2, sau đó ghép a3 với a4 rồi ghép 2 số còn lai 
    -...
    nếu bạn nhìn kĩ hơn thì bạn có thể hoàn toàn nhận ra rằng bạn có thể chia bài toán thành 2 phần
    đó là 2 bài toán con a1, a2 và a3, a4 và việc của bạn chỉ là giải quyết cả 2 bài toán con này
    và sau đó lấy min của hai khoảng
b3: xác định công thức truy hồi, đáp án bài toán
    từ ví dụ ở bước 1 và 2 ta thấy rằng ta có thể chia bài toán con thành các phần khác nhau
    và cách tốt nhất là chia thành 2 phần, tại sao ?
    - vì 2 phần ta sẽ xử lý ngắn gọn, đỡ dài dòng hơn 3, 4 phần
    - ta nhận thấy rằng dù cho có bao nhiêu phần tử đi nữa thì để gọp một đoạn con gồm x phần tử
    thì thao tác cuối cùng của ta luôn phải là gộp hai phần lại với nhau để tạo thành 1 phần

    ta có một nhận xét : 
    a1, a2, a3, a4, .. an có thể chia thành 2 phần là a1, a2, ..ak và a(k + 1), ..an (1 <= k < n)
    từ cơ sở đó ta gọi dp[i][j] là chi phí nhỏ nhất để gộp đoạn con từ vị trí i đến vị trí j thành một số
    => dp[i][j] = min(dp[i][k] + dp[k + 1][j]) + ai + a(i + 1), ..+ aj (i <= k < j)
    với dp[i][k] + dp[k + 1][j] là chi phí trước đó và ai + a(i + 1), ..+ aj là chi phí hiện tại
    để gộp 2 phần lại với nhau

6

Groot commented on May 24, 2024, 9:52 a.m.

GỢI Ý: Dùng quy hoạch động

dp[i][j]: Chi phí tối thiểu để ghép các cục thạch từ vị trí i đến j trong dãy. kết quả: dp[0][n-1]

prefix[i]: Tổng kích thước thạch từ 1 đến i

Khởi tạo dp[i][i] = 0 (cục thạch ghép chính nó có chi là 0)

Với mỗi đoạn từ i đến j, chúng ta xem xét mọi vị trí k nằm giữa i và j để tìm cách tách đoạn thành hai phần tại k. Chi phí ghép hai phần này sẽ bao gồm chi phí tối thiểu để ghép từ i đến k và từ k+1 đến j, cộng với chi phí để ghép hai phần này thành một

công thức: dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + sum[j] - (i > 0 ? sum[i-1] : 0))