Luogu P1005 - Matrix fetching game

Alice wants to play a matrix fetching game on a n×mn \times m matrix, where the elements of the matrix aija_{ij} are all non-negative integers. The rules of the game are as follows:

  • Alice has mm round of fetching.

  • For each fetching, she needs to take away one element from each row of the matrix.

  • Each element taken at a time can only be the first or last one of the row.

  • After each fetching, she will get a score. The score is the sum of all scores earned from fetching each row. The scores earned from each row is equal to e2ie \cdot 2^i, where ee is the value of the element taken, and ii is the ithi \th round of fetching (labeled from 11 to mm).

  • After mm rounds, all of the elements of the matrix will be taken, and the score earned from each fetching will be added to get the final score.

Your goal is to find the optimal strategy for Alice to get maximum final score possible.

How to submit:

The pastebin below has 1010 inputs. Each input has the format:

  • Two numbers n,mn,m, the number of rows and columns of the matrix.

  • n×mn \times m numbers, the values of each element of the matrix.

You should output: A number MM, the maximum final score Alice can get.

Then submit the sum of all of the outputs.

Input restrictions:

Input 161 \sim 6: 1n,m301 \leq n,m \leq 30.

Input 7107 \sim 10: 1n,m801 \leq n,m \leq 80.

Inputs are here

Luogu Problem Set


Problem Loading...

Note Loading...

Set Loading...