Luogu P1005 - Matrix fetching game

Computer Science Level 5

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

Alice has $m$ 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 $e \cdot 2^i$ , where $e$ is the value of the element taken, and $i$ is the $i \th$ round of fetching (labeled from $1$ to $m$ ).
After $m$ 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 $10$ inputs. Each input has the format:

Two numbers $n,m$ , the number of rows and columns of the matrix.
$n \times m$ numbers, the values of each element of the matrix.

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

Then submit the sum of all of the outputs.

Input restrictions:

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

Input $7 \sim 10$ : $1 \leq n,m \leq 80$ .

Inputs are here

Luogu Problem Set

The answer is 168149058344279303484369019192.

1 solution

Sahil Goyat
Jan 14, 2021

def fetch(l,k):
    L=[[float('-inf') if k in (n,k-m-1) else 0 for m in range(k,-2,-1)] for n in range(0,k+1)]
    for n in range(k-1,-1,-1):
        for m in range(n,k):
            if n==m:
                L[n][m]=2*l[n]
            else:
                L[n][m]=max(l[n]+L[n+1][m],l[m]+L[n][m-1])*2
    return L[0][k-1]
def op(A,n,m):
    return sum([fetch(l,m) for l in A])
s=i=0
with open('1005.txt','r') as f:
    r=f.readlines()
    while i<len(r):
        R=r[i][0:-1].split(' ')
        if R[0].isnumeric() and R[1].isnumeric():
            M=[[int(j) for j in k.split(' ') if j not in['',' ','\n']] for k in r[i+1:i+int(R[0])+1]]
            s+=op(M,int(R[0]),int(R[1]))
            i+=int(R[0])+1
        else:
            i+=1
print(s)

Luogu P1005 - Matrix fetching game

The answer is 168149058344279303484369019192.

1 solution

1 pending report

Vote up reports you agree with