LA 3530

From Algorithmist

Contents 1 LA 3530 - Martian Mining 2 Summary 3 Explanation 4 Input 5 Output

[edit] LA 3530 - Martian Mining

• http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3530

[edit] Summary

Given is a matrix, each cell contains some amounts of two types of materials. In each cell you can build a conveyor belt going upwards or a conveyor belt going to the left (or nothing, but not both conveyor belts at the same time). The conveyor belts of the first type transport the first type of materials, and vice versa.

The task is to maximize the total amount of materials the conveyor belts transport to the boundary of the matrix.

[edit] Explanation

Clearly there is an optimal solution with a conveyor belt in each cell and with no useless conveyor belts. In other words, there is an optimal solution such that:

• Each cell contains a conveyor belt
• If a cell contains a belt going upwards, all the cells above it contain a belt going upwards.
• The same for belts going to the left.

The only thing we have to do is to determine the optimal boundary between the two types of conveyor belts. This can be done in O(RC) using dynamic programming.

[edit] Input

4 4
0 0 10 9
1 3 10 0
4 2 1 3
1 1 20 0
10 0 0 0
1 1 1 30
0 0 5 5
5 10 10 10
0 0

[edit] Output

98