题目详情题解（0）讨论（0）提交记录（0）

AT_past202104_i.魚釣り

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个 h×wh \times w 的长方形网格。开始时你在 (1,1)(1,1)，你最终要到达 (h,w)(h,w)。每次你可以从当前格子走到它右边的格子或它下边的格子上，不能越界。

每次你经过一个格子的时候，你可以选择取或者不取这个格子里的数。你被允许最多取 kk 个数。请按照 k=1,2,...,h+w−1k=1,2,...,h+w-1 的顺序给出这种情况下你可以取到的数的和的最大值。

输入格式

第一行输入行数 hh 和列数 ww。

接下来输入 hh 行，每行 ww 个数，上数第 ii 行左数第 jj 列的数即为 (i,j)(i,j) 内的数。

输出格式

输出 (h+w−1)(h+w-1) 行，每行一个整数，第 ii 行的整数为 k=ik=i 时取到的数的和的最大值。

输入输出样例

  • 输入#1

    5 6
4 5 1 2 6 9
1 3 3 2 7 4
8 3 7 6 2 1
7 8 3 3 7 5
8 4 5 5 5 6

    输出#1

    9
16
23
30
36
41
45
48
52
53

说明/提示

数据规模与约定

对于 100%100\% 的数据，保证：

  • 输入数值均为整数；
  • 1≤h,w≤1001 \le h,w \le 100，1≤1 \le 方格里的所有数 ≤109\le 10^9。

输入解题思路，AI测评打分。不知道怎么写?

首页