CUTRECT - Cắt hình chữ nhật
Giới hạn- Thời gian: 0.6s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Có một mảnh giấy hình chữ nhật được chia ra làm lưới MxN ô vuông đơn vị.
Nhiệm vụ của bạn là phải cắt mảnh giấy ra làm hai phần thỏa mãn các điều kiện sau:
- Đỉnh trái trên và đỉnh phải dưới của hình chữ nhật thuộc về hai phần khác nhau.
- Mỗi ô vuông đơn vị nằm trọn vẹn trong một phần. Nói cách khác, bạn chỉ được cắt dọc theo các cạnh của lưới.
Do chi phí để cắt mỗi cạnh đơn vị là khác nhau, bạn cần tìm cách cắt có tổng chi phí của các cạnh mà đường cắt đi qua là nhỏ nhất.
Dữ liệu
- Dòng đầu ghi 2 số nguyên dương M, N thể hiện lưới có M dòng, mỗi dòng có N ô vuông đơn vị.(M, N ≤ 400)
- M dòng tiếp theo, mỗi dòng ghi N - 1 số tự nhiên thể hiện chi phí cắt mỗi cạnh dọc.
- M - 1 dòng tiếp theo, mỗi dòng ghi N số tự nhiên thể hiện chi phí cắt mỗi cạnh ngang.
- Chi phí cắt mỗi cạnh nằm trong phạm vi số nguyên 32-bit có dấu. Các cạnh được liệt kê theo từng dòng từ trên xuống dưới. Các cạnh thuộc cùng một dòng được liệt kê từ trái qua phải.
Kết quả
- Một số tự nhiên duy nhất thể hiện chi phí cắt nhỏ nhất. Nếu không có cách cắt nào thỏa mãn thì in ra -1.
Ví dụ
Input: 2 3 3 1 1 3 3 1 3 Output: 3
Tác giả: Khúc Anh Tuấn
- Người up: voj
- Nguồn bài: VNOI '10