#G. 三倍经验

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \

Type: RemoteJudge

1000ms

256MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

数字金字塔由 $n$ 行整数组成，第 $i(1\le i\le n)$ 行有 $i$ 个数字，一个示例如下。

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

现在你在金字塔的顶部（第一行），你希望走到金字塔的底部（第 $n$ 行），每一步你只能走向当前所在位置的左下方的数字或者右下方的数字。同时作为一个强大的小朋友，你可以选择金字塔中的不多于 $k$ 个数字让他们成为原来的 $3$ 倍。

你会收集你路上经过的所有位置上的数字，最后的得分即为收集的数字之和，求最大得分。

输入格式

第一行输入两个整数 $n,k$ ，表示数字金字塔的行数和乘 $3$ 的数字个数最大值；接下来 $n$ 行，其中的第 $i$ 行有 $i$ 个以空格隔开的整数依次表示数字金字塔第 $i$ 行的数字 $a_{i,1},a_{i,2},a_{i,3}...a_{i,i}$ 。

输出格式

一行一个整数，表示最大得分。

样例 #1

样例输入 #1

样例输出 #1

提示

对于 $30\%$ 的数据，满足 $k\le n\le 6$ ，并且对于任意 $1\le i\le n$ ， $1\le j\le i$ 满足 $0\le a_{i,j}\le 100$ ；对于 $100\%$ 的数据，满足 $1\le n\le100$ ， $0\le k\le \dfrac{n(n+1)}{2}$ ，且对于任意 $1\le i\le n$ ， $1\le j\le i$ 满足 $|a_{i,j}|\le 10^9$ 。

北辰OI俱乐部算法提高班：动态规划专题（一）

Not Claimed

Status: Done
Problem: 28
Open Since: 2023-11-25 0:00
Deadline: 2024-12-26 23:59
Extension: 24 hour(s)

#G. 三倍经验

三倍经验

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

提示

北辰OI俱乐部算法提高班：动态规划专题（一）

Status

Development

Support

#G. 三倍经验

三倍经验

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

提示

北辰OI俱乐部算法提高班：动态规划专题（一）

Status

Development

Support

Don't have an account?

SIGN IN