Trò chơi thả bóng được chơi trên một bảng gồm block, mỗi block gồm hàng và cột (bảng lặp lại lần). Các hàng được đánh số từ đến từ trên xuống dưới, các cột được đánh số từ đến từ trái sang phải. Ô ở hàng , cột được gọi là ô .
Ở mỗi ô của bảng, có một vách ngăn chéo chạy theo một trong hai hướng: trên trái xuống dưới phải, hoặc trên phải xuống dưới trái.
Nếu bạn thả quả bóng ở một cột nào đó, theo trọng lực quả bóng sẽ rơi xuống dưới. Quả bóng sẽ không thể đi xuyên các vách ngăn nên sẽ xảy ra các trường hợp sau:
Quả bóng bị kẹt ở trong bảng và không thể di chuyển nữa;
Quả bóng rơi ra ngoài bảng ở cạnh bên trái;
Quả bóng rơi ra ngoài bảng ở cạnh bên phải;
Quả bóng rơi ra ngoài bảng ở đáy của bảng ở cột .
Nếu trường hợp đến xảy ra, ta gọi , nếu trường hợp cuối xảy ra ta gọi .
Ví dụ nếu ta thả quả bóng ở cột thì quả bóng sẽ rơi ra ngoài ở cạnh bên phải.
Nếu chúng ta thả quả bóng ở cột thì quả bóng sẽ rơi ra ngoài bảng ở cột .
Ngoài ra, chúng ta có thể thực hiện phép thay đổi chiều vách ngăn với các ô trên bảng. Ví dụ sau đây là bảng sau khi ta thực hiện phép thay đổi với ô . Phép thay đổi ở ô sẽ có chi phí là :
Bây giờ, nếu chúng ta thả quả bóng ở cột thì quả bóng sẽ rơi ra ngoài bảng ở cột .
Trong bài toán này, cho cấu hình bảng ban đầu, chi phí thay đổi vách ngăn, là số lượng quả bóng sẽ được thả, mảng gồm phần tử là chỉ số các cột sẽ thả bóng, mảng gồm phần tử là giá trị . Bạn có thể thực hiện một số phép đổi chiều vách ngăn, sau đó thả lần lượt quả bóng. Hãy tính chi phí tối thiểu để đạt được kết quả mong muốn.
Dữ liệu:
Dòng thứ nhất ghi ba số và ;
Tiếp theo là dòng, mỗi dòng ghi xâu kí tự để mô tả một block của bảng ban đầu. Các xâu chỉ chứa các kí tự \ tương ứng với vách ngăn từ trái trên xuống phải dưới hoặc / tương ứng với vách ngăn từ phải trên xuống trái dưới;
Tiếp theo là dòng, mỗi dòng ghi số nguyên dương, mô tả chi phí thay đổi vách ngăn của các ô ;
Dòng tiếp theo chỉ chứa duy nhất số ;
Dòng tiếp theo ghi số có giá trị tăng dần );
Dòng cuối cùng ghi số hoặc .
Kết quả:
Ghi ra một dòng là chi phí tối thiểu tìm được.
Giới hạn:
Có số test ứng với số điểm của bài có và ;
Có số test khác ứng với số điểm của bài có và ;
Có số test khác ứng với số điểm của bài có và ;
Có số test khác ứng với số điểm của bài có ;
Có số test còn lại ứng với số điểm của bài không có giới hạn gì thêm.
