MCITYHAL - Repair City Hall

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/mcityhal


Sửa tường : ma trận kích thước M hàng,  N cột biểu diễn tường, 1-tường tốt,
0-tường hỏng.
 
1110000111
1100001111
1000000011
1111101111
1110000111 
 
Figure-1 
 
Sửa = cách đặt các khối thẳng đứng vào các vùng hỏng. Các khối có thể sử dụng
có độ rộng 1 và chiều cao có thể là {1,2, ..., M}.  
 
Cần xác định số khối từng loại sao cho số lượng khối là ít nhất. 

Input

Dòng đầu là hai số M và N (1 <= M, N <= 200). M dòng sau đó gồm N kí tự 
1 hoặc 0. 

Sample Input
5 10 
1110000111
1100001111
1000000011
1111101111
1110000111

Output

 
Xác định số khối cần sử dụng đối với từng chiều cao  
k Ck 
 
với k ∈ {1,2, ..., M} là chiều cao của khối và Ck là số khối cần sử dụng.
Không in ra các dòng có Ck = 0 và in ra theo thứ tự tăng dần của k. 

Sample output
1 7 
2 1 
3 2 
5 1 

Được gửi lên bởi:psetter
Ngày:2009-02-23
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Peiking 2004

hide comments
2017-10-30 15:00:28
ông cmt dưới làm gì gkê vậy :)) 2 for AC r
2017-08-31 04:14:13
3 vòng lặp + map -> 1hit ac
2016-07-21 11:46:50
Do Hong Huan chém gió vớ vẩn

Last edit: 2016-07-21 11:47:34
2015-11-19 15:50:55 Do Hong Huan
Bài này phải DFS+BFS+BIT+IT+Kruskal+BIGNUM+..v.v.. mới AC
2015-03-25 13:57:29
Không cần DFS, duyệt theo từng cột... 1 phát AC :)))))
2014-10-09 16:00:59 CTKB LHP
Đề troll =_=
Nếu cắt bất kì thì chắc hay hơn =)) =))
2014-09-21 18:22:09 Prismatic
O(n*(m+1)) :))
2014-09-21 18:22:09 Prismatic
O(n*(m+1)) :))
2014-08-24 03:37:57 ■■‡[ND] Bee Sociu■■‡
Code chuan 20 dong =))))
2014-08-13 06:16:55 Duc M. Pham
Bài này cần quái gì DFS nhỉ? DFS "mấy lớp" lại càng không @@
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.