Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
LAZYCOWS - Lazy Cows |
English | Vietnamese |
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/lazycows
Cho mô hình bãi cỏ có dạng bảng chữ nhật 2xB (1 <= B <= 15,000,000), trong đó một số ô có con bò đang ăn cỏ. Có tất cả N con bò (1 <= N <= 1000) trên bãi cỏ. Ví dụ:
------------------------------------------------------- | | cow | | | | cow | cow | cow | cow | ------------------------------------------------------- | | cow | cow | cow | | | | | | -------------------------------------------------------
Bác John muốn dùng K (1 <= K <= N) cái chuồng hình chữ nhật để che phủ đàn bò, sao cho tổng diện tích được phủ là nhỏ nhất. Không có hai chuồng nào được nằm đè lên nhau. Hiển nhiên, các chuồng phải che phủ hết các ô có bò.
Ví dụ, trong hình trên nếu K=2, lời giải tối ưu bao gồm một chuồng kích thước 2x3 và một chuồng kích thước 1x4. Tổng diện tích được phủ là 10.
Dữ liệu
Dòng đầu tiên chứa một số nguyên t là số bộ test. Mỗi bộ test có dạng:
- Dòng 1: N, K, B
- Dòng 2..N+1: chức tọa độ của các con bò, trong phạm vi (1,1) đến (2,B). Không có ô nào chứa hơn 1 con bò.
Kết quả
Với mỗi test, in ra tổng diện tích nhỏ nhất cần phủ.
Ví dụ
Dữ liệu 1 8 2 9 1 2 1 6 1 7 1 8 1 9 2 2 2 3 2 4 Kết quả 10
Được gửi lên bởi: | Jimmy |
Ngày: | 2005-05-03 |
Thời gian chạy: | 9s |
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: | US Open International 2005 Gold Division |
hide comments
2018-05-30 16:19:02
chỉ hướng giải với |
|
2017-07-27 09:33:43
Last edit: 2017-07-27 12:42:24 |
|
2014-03-25 16:55:51 Anh Duc Le
Bài này cài đặt dễ sai thật. Debug vật vã mới AC. |