#P2045. 方格取数加强版
方格取数加强版
题目描述
给出一个 的矩阵,每一格有一个非负整数 (),现在从 出发,可以往右或者往下走,最后到达 ,每达到一格,把该格子的数取出来,该格子的数就变成 ,这样一共走 次,现在要求 次所达到的方格的数的和最大。
输入格式
第一行两个数 (,)。
接下来 行,每行 个数,分别表示矩阵的每个格子的数。
输出格式
一个数,为最大和。
3 1
1 2 3
0 2 1
1 4 2
11
提示
每个格子中的数不超过 。
给出一个 n×n 的矩阵,每一格有一个非负整数 Ai,j(Ai,j≤103),现在从 (1,1) 出发,可以往右或者往下走,最后到达 (n,n),每达到一格,把该格子的数取出来,该格子的数就变成 0,这样一共走 K 次,现在要求 K 次所达到的方格的数的和最大。
第一行两个数 n,K(1≤n≤50,0≤K≤10)。
接下来 n 行,每行 n 个数,分别表示矩阵的每个格子的数。
一个数,为最大和。
3 1
1 2 3
0 2 1
1 4 2
11
每个格子中的数不超过 1000。