我要招人

去企业版

首页 > 试题广场 >

单帧操作

[编程题]单帧操作

热度指数：940 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定n个数字的序列 $a_0,a_1,\dots a_{n-1}$ ，对位置i进行一次操作将使得 $a_{i-1},a_i,a_{i+1}$ 都变成 $max(a_{i-1},a_i,a_{i+1})$

特别的，对位置0进行操作将使得 $a_0$ 和 $a_1$ 都变成 $max(a_0,a_1)$

对位置n-1进行操作将使得 $a_{n-2}$ 和 $a_{n-1}$ 都变成 $max(a_{n-2},a_{n-1})$

并且操作过位置i之后，位置0到i都不能再操作

设最多可以操作 $k( k\le n )$ 次，最后得到的整个序列的总和最大可以是 $m_k$

你需要求出 $m_1,m_2,...m_n$

示例1

输入

5,[1,2,3,4,5]

输出

[18,21,22,22,22]

说明

输入：
n=5, 输入序列为[1,2,3,4,5]

[1,2,3,4,5]对应位置0,1,2,3,4
只能操作1次的时候，对位置1操作得到[3,3,3,4,5]，或者对位置2操作可以得到[1,4,4,4,5]，或者对位置3操作可以得到[1,2,5,5,5]，都可以得
只能操作2次的时候，按次序操作位置1和位置3可以得到[3,3,5,5,5]，其他操作不会得到更优的结果，所以
能操作3次以上的时候可以得到的最优序列为[3,4,5,5,5]（依次操作位置1，位置2，位置3）,所以

备注:

算法知识视频讲解

积极的防守者

发表于 2020-02-05 21:42:10

普通解法：二进制枚举所有位置选或者不选，然后按顺序模拟操作，并更新相应的答案，时间复杂度，因为要开一个辅助数组来进行模拟操作，所以空间复杂度 vector<int> solve(int n, vector<int> a){ assert(n <= 20); 展开全文

Maokt

发表于 2021-08-02 11:50:13

算法思想一：暴力枚举解题思路：题目的主要信息：给一串数组，每次找到一个位置进行一次操作：将该位置前后一个数及本身改为三者中的最大值一共进行n次操作，每次操作需要找到改变后使数组和最大那个位置来改变利用二进制掩码的特性，枚举所有位置选择或是不选择的组合（相当于n次操作，选择展开全文

牛一霸

发表于 2021-08-07 09:10:15

题目：单帧操作描述：给定n个数字的序列a0,a1,…an−1，对位置i进行一次操作将使得ai−1,ai,ai+1都变成max(ai−1,ai,ai+1)，特别的，对位置0进行操作将使得a0和a1都变成max(a0,a1)，对位置n-1进行操作将使得an−2和an−1都变成max(an−2,an−1) 展开全文

摸鱼学大师

发表于 2021-07-30 17:07:39

思路：题目的主要信息：给一串数组，每次找到一个位置进行一次操作：将该位置前后一个数及本身改为三者中的最大值一共进行n次操作，每次操作需要找到改变后使数组和最大那个位置来改变方法一：暴力解法（超时）具体做法：利用二进制掩码的特性，枚举所有位置选择或是不选择的组合（相当于n次操作，选择的位置展开全文

球球了给孩子一个offer吧

发表于 2021-08-06 16:02:44

题目：给定n个数字的序列，对位置i进行一次操作将使得都变成特别的，对位置0进行操作将使得和都变成对位置进行操作将使得和都变成并且操作过位置i之后，位置0到i都不能再操作设最多可以操作k(k≤n)次，最后得到的整个序列的总和最大可以是你需要求出方法一：四维动态规划定义：表示第个位置进行第j次操作值为的展开全文

认认真真coding

发表于 2021-08-04 11:25:45

题目描述给定n个数字的序列a0,a1,…an−1，对位置i进行一次操作将使得ai−1,ai,ai+1都变成max(ai−1,ai,ai+1)特别的，对位置0进行操作将使得a0和a1都变成max(a0,a1)对位置n-1进行操作将使得an−2和an−1都变成max(an−2,an−1)并且操作过位置i 展开全文

CroMarmot

发表于 2021-10-02 03:47:23

题意长度为nnn的数组, 每次把相邻的三个数，都变为它们中的最大值，操作的下标从左向右问，操作iii次后的数组的最大和, 其中iii从111取到nnn,给出不同iii对应的最大值。 n≤200n\leq 200n≤200 数组中每个数值111到200200200之间的整数算法深搜(TLE) 展开全文

问题信息

动态规划广度优先搜索(BFS)

难度：

2条回答 14收藏 3528浏览

通过挑战的用户

查看代码

colddrink

2022-01-04 20:52:42
陈墨瞳1995

2021-12-23 17:39:29
牛客70924...

2021-10-19 22:18:03
philos

2021-10-16 23:19:53
CroMarmot

2021-10-02 02:43:52

单帧操作

输入

输出

说明

备注:

问题信息

热门推荐

通过挑战的用户

相关试题