MCARDS - Card Sorting

no tags 

Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274505/problem/M

 

Mav có n*c quân bài; mỗi quân bài 1 màu; và mỗi màu có n quân bài. Mav muốn sắp xếp các quân bài cùng màu nằm cạnh nhau và chúng theo thứ tự tăng dần về giá trị.

Input

Dòng đầu là 2 số C (số màu), (1 ≤ C ≤ 4), và N, số quân bài cùng màu mỗi loại, (1 ≤ N ≤ 100).

N*C dòng tiếp theo mỗi dòng là 2 số nguyên X, Y; 1 ≤ X ≤ C, 1 ≤ Y ≤ N, là màu của quân bài và giá trị quân bài đó.

Thứ tự quân bài ban đầu (từ trái sang phải) chính là thứ tự dữ liệu input.

 

Output

 

Số lần chuyển bài ít nhất để thu được dãy bài được sắp theo yêu cầu trên.

 

Sample

CARDS.IN

2 2
2 1
1 2
1 1
2 2

CARDS.OUT

2
 
CARDS.IN

4 1
2 1
3 1
1 1
4 1

CARDS.OUT

0
 
CARDS.IN

3 2
3 2
2 2
1 1
3 1
2 1
1 2

CARDS.OUT
2


hide comments
ayush_negi: 2021-03-14 23:58:55

must do question of DP (tricky question of LIS (dp))


Added by:~!(*(@*!@^&
Date:2009-03-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:COI 01