Partition DP

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 CSES - Rectangle Cutting | Cắt hình chữ nhật 100 (p) 1.0s 512M
2 Atcoder Educational DP Contest - Problem N: Slimes 100 (p) 1.0s 256M
3 Zuma 100 (p) 1.0s 512M

1. CSES - Rectangle Cutting | Cắt hình chữ nhật

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Với một hình chữ nhật \(a \times b\), nhiệm vụ của bạn là cắt nó thành các hình vuông. Trong mỗi bước, bạn có thể chọn một hình chữ nhật và cắt nó thành hai hình chữ nhật sao cho độ dài các cạnh vẫn là số nguyên. Số bước tối thiểu là bao nhiêu?

Input

  • Gồm một dòng duy nhất chứa hai số nguyên \(a\) và \(b\).

Output

  • In một số nguyên: số lần di chuyển tối thiểu.

Constraints

  • \(1 \leq a, b \leq 500\)

Example

Test 1

Input 
3 5
Output 
3

2. Atcoder Educational DP Contest - Problem N: Slimes

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Có \(N\) slime được xếp thành hàng ngang. Slime thứ \(i\) có kích thước \(a_i\).

Taro muốn ghép các slime thành 1 slime lớn hơn. Cậu ấy thực hiện các thao tác sau cho đến khi chỉ còn lại 1 slime:

  • Chọn hai slime liền kề và ghép chúng lại thành slime mới. Slime mới có kích thước là \(x + y\) (với \(x, y\) là kích thước của slime trước khi ghép) và mất chi phí là \(x + y\). Vị trí các slime không thay đổi.

Hãy tìm tổng chi phí nhỏ nhất có thể.

Input

  • Dòng đầu tiên gồm một số nguyên \(N\) (\(1 \leq N \leq 400\)).
  • Dòng thứ hai gồm \(N\) số nguyên \(a_i\) (\(1 \leq a_i \leq 10^9\)).

Output

  • Một dòng duy nhất in ra tổng chi phí nhỏ nhất có thể.

Example

Test 1
Input 
4
10 20 30 40
Output 
190
Note

Taro làm như sau:
\( (10, 20, 30, 40) -> (30, 30, 40) -> (60, 40) -> (100) \)

Test 2
Input 
5
10 10 10 10 10
Output 
120

3. Zuma

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Genos gần đây đã cài đặt trò chơi Zuma trên điện thoại của mình. Trong trò chơi Zuma, có một hàng gồm \(n\) viên đá quý, viên thứ \(i\) có màu \(c_i\). Mục tiêu của trò chơi là tiêu diệt tất cả các viên đá quý trong hàng càng nhanh càng tốt.

Trong một giây, Genos có thể chọn một đoạn con liên tiếp các viên đá quý tạo thành một chuỗi đối xứng (palindrome) và loại bỏ nó khỏi hàng. Sau khi đoạn con bị loại bỏ, các viên đá quý còn lại sẽ dịch chuyển để tạo thành một hàng liên tục. Số giây tối thiểu cần thiết để tiêu diệt toàn bộ hàng là bao nhiêu?

Nhắc lại rằng, một chuỗi (hoặc đoạn con) được gọi là đối xứng nếu nó đọc từ trái sang phải hay từ phải sang trái đều giống nhau. Như vậy, đoạn đối xứng trong hợp này sẽ có màu của viên đá quý đầu tiên bằng màu của viên cuối cùng, màu của viên thứ hai bằng màu của viên kế cuối, và cứ tiếp tục như vậy.

Input

  • Dòng đầu tiên chứa một số nguyên duy nhất \(n\) (\(1 \le n \le 500\)) — số lượng viên đá quý.
  • Dòng thứ hai chứa \(n\) số nguyên cách nhau bởi dấu cách, số thứ \(i\) là \(c_i\) (\(1 \le c_i \le n\)) — màu của viên đá quý thứ \(i\) trong hàng.

Output

  • In ra một số nguyên duy nhất — số giây tối thiểu cần thiết để tiêu diệt toàn bộ hàng.

Example

Test 1

Input 
3
1 2 1
Output 
1
Note

Trong ví dụ đầu tiên, Genos có thể tiêu diệt toàn bộ hàng trong một giây vì 1 2 1 là một chuỗi đối xứng.

Test 2

Input 
3
1 2 3
Output 
3
Note

Trong ví dụ thứ hai, Genos chỉ có thể tiêu diệt từng viên đá quý một, vì vậy việc tiêu diệt ba viên đá quý mất ba giây.

Test 3

Input 
7
1 4 4 2 3 2 1
Output 
2
Note

Trong ví dụ thứ ba, để đạt được thời gian tối ưu là hai giây, trước tiên hãy tiêu diệt chuỗi đối xứng 4 4, sau đó tiêu diệt chuỗi đối xứng 1 2 3 2 1.

Nguồn: - Codeforces 607B