Tô màu
Xem PDF
Điểm:
1900 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Trên một đường thẳng cho \(n\) hình vuông xếp thành một hàng đánh số 1, 2, ..., \(n\) từ trái qua phải. Hình vuông thứ \(i\) có màu là \(c_i\).
Ta nói rằng một dãy hình vuông từ vị trí \(i\) đến vị trí \(j\) là một mảng màu nếu như \(c_i=c_j\) và \(c_i=c_k\) với mọi \(i<k<j\). Nói cách khác tất các các hình vuông từ vị trí \(i\) đến vị trí \(j\) là cùng một màu.
Mỗi thao tác bạn có thể tô lại màu cho các hình vuông trong một mảng màu thành màu mới.
Hỏi rằng số thao tác ít nhất cần thực hiện để đưa tất cả \(n\) hình vuông về cùng một màu là bao nhiêu
Input
- Dòng đầu tiên ghi số nguyên dương \(n\) (\(n\le 5000\)) - số hình vuông
- Dòng thứ hai ghi \(n\) số nguyên dương \(c_1,c_2,…,c_n\) (\(1\le c_i\le 5000\)) - màu ban đầu của các hình vuông.
Output
- In ra một số nguyên là số thao tác nhỏ nhất cần thực hiện
Example
Test 1
Input
4
5 2 2 1 Output
2Note
Trong ví dụ thứ nhất biển đổi: \([5, 2, 2, 1] \rightarrow [5, 5, 5, 1] \rightarrow [1, 1, 1, 1]\)
Test 2
Input
8
4 5 2 2 1 3 5 5 Output
4
Bình luận
Trước hết , bài này dựa trên một trò chơi là Flood game , Link Trò Chơi (kỉ lục của mình là 21 nước đi).
Có 2 cách tiếp cận :
-Cách 1 : sử dụng dp[N][N][2] với 2 chiều là l , r và chiều thứ 3 là 0 hoặc 1.DP[l][r][0] là số thao tác ít nhất để đưa đoạn l,r về cùng một màu c[l] và tương tự , dp[l][r]1 là cùng với màu c[r].Từ dp[l][r][type] , ta sẽ tối ưu cho dp[l - 1][r][0] và dp[l][r - 1]1.
-Cách 2 : với mỗi màu cạnh nhau và giống nhau , ta sẽ nén về thành 1 màu . Với mỗi ô bắt đầu , ta tìm LCS dài nhất mở rộng sang 2 bên.Kết quả sẽ là N - max(LCS của các ô bắt đầu)
https://ideone.com/BPIYsW
thg nào chép méc admin ko đc chép tham khảo dom dom yes yes
Bài này hình như dịch sang sai . Thực chất bài này dễ hơn nhiều, bài toán gốc đây mn:https://codeforces.com/contest/1114/problem/D