P3477.第2题-寻宝之旅

1000ms

Tried: 320

Accepted: 107

Difficulty: 3

所属公司 : 滴滴

算法与标签>动态规划

题目内容

有一座巨大的官殿，可以被视为由 $n$ 行 $n$ 列房间组成，从上到下分别为第 $1,2,...n$ 行,从左到右分别为第 $1,2,...n$ 列。第 $i$ 行第 $j$ 列房间内有价值为 $a_{i,j}$ 的宝藏。

每个房间都有一扇通往下一行同一列的常开的门，即从第 $i$ 行第 $j$ 列房间能移动到第 $i+1$ 行第 $j$ 列房间，但是如果选择带走房间内的宝藏，则该侧门会关闭。特别地，第 $n$ 行的所有房间的通往下一行同一列的门都通往宫殿外。

除此之外，每个房间都有通往同一行下一列的门，即第 $i$ 行第 $j$ 列房间有一扇通往第 $i$ 行第 $j+1$ 列房间的门, 该门不常开，但是如果选择带走房间内的宝藏，则该侧门会打开。特别地，第 $n$ 列的所有房间的通往同一行下一列房间的门都通往宫殿外。

小钟从第一行第一列房间出发，他想知道在离开宫殿前他最多能够带走多少价值的宝藏。请你帮忙计算答案。

输入描述

输入包括多组测试数据。

输入第一行包括一个正整数 $T(1<=T<=10)$ ,表示测试数据的组数。

每组测试数据的第一行有一个整数 $n(1<=n<=500)$ ,表示宫殿由 $n$ 行 $n$ 列房间组成;

接下来的 $n$ 行第 $i$ 行有 $n$ 个整数 $a_{i,1},a_{i,2},...,a_{i,n}(0<=a_{i,j}<=10^5)$ ,依次表示第 $i$ 行第 $1,2,....n$ 列房间内宝藏的价值大小。

保证每个测试点的所有测试数据的 $n^2$ 的和不超过 $2.5*10^5$

输出描述

对于每组测试数据,输出一个正整数表示小钟离开宫殿前最多能够带走多少价值的宝藏。

样例1

输入

输出

24
5

说明

对于第一组测试数据，小钟的移动轨迹可以是这样的: $(1,1)\rightarrow(2,1)$ $\rightarrow(3,1)\rightarrow(3,2)$ $\rightarrow(3,3)\rightarrow$ 官殿外，分别在 $(3,1)，(3,2)，(3,3)$ 处带走宝藏，总价值大小为 $7+8+9=24$

对于第二组测试数据，小钟的移动轨迹可以是这样的: $(1,1)\rightarrow(1,2)\rightarrow$ 宫殿外，分别在 $(1,1),(1,2)$ 处带走宝藏，总价值大小为 $0+5 =5$

输入

预期输出（选填）

思路

P3477.第2题-寻宝之旅

题目内容

输入描述

输出描述

样例1

Status

Development

Support

About