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
2014-07-09 09:31:55 Con Bò Huyền Thoại
dễ :v
2014-06-06 04:22:40 Kraken
ặc! mấy con số liền nhau làm mình sub cả chục lần @@!
2014-06-05 10:58:30 Thcs Ðặng Chánh Kỷ
duyệt cơ bản
2014-05-31 19:13:59 Thần Ðồng Mẫu Giáo
O(n*m) 1 đấm AC :))))
2014-05-21 16:19:04  
Bài này cần gì dfs :))
2014-05-05 17:29:37 Lollipop
DFS mấy lớp, khó thế :(
2014-04-13 12:40:35 Nắng
DFS @@@@
2013-08-16 02:43:32 huy
Lỗi chỗ nào cà 8}

#include <iostream>
using namespace std;

int main()
{
/*
5 10
1110000111 //m doc 5
1100001111 //n ngang 10
1000000011
1111101111
1110000111
*/

long unsigned int m, n, *k, *ck, temp;
bool *p;

cin>> m>> n;
k = ck = new unsigned long int[n-1];
p = new bool [m*n-1];

for (int i = 0; i < m; i++)
{
cin>> temp;
for (int j = 0; j < n; j++)
{
p[n * i + j] = temp%10;
temp /= 10;
}
}

for (int i = 0; i < n; i++)
k[i] = 0;

for (int i = 0; i < n; i++) //ngang
{
temp = 0;
for (int j = 0; j < m; j++) //doc
{
bool first = true;
if (p[n * j + i] == 0)
temp++; //tăng chiều dài cục gạch
else //het hu -> luu so gach
if (temp > 0)
{
k[temp]++;
temp = 0;
}
if (j == m - 1 && temp > 0) //cuoi cung -> luu so gach
{
k[temp]++;
temp = 0;
}
}
}
for (int i = 0; i < n; i ++)
if (k[i] > 0)
{
cout<< i<< " "<< k[i];
if (i == n - 1)
break;
cout<< endl;
}
return 0;
}



2013-08-12 09:15:17 Blazing Heart
bai nay kho vai~
DFS may lop' ms duoc.
2013-06-25 10:20:59 Hoài
hic test thử đúng mà gửi bài lên toàn sai không à
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.