首页 > 试题广场 >

小红的数组切割

[编程题]小红的数组切割
  • 热度指数：217 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小红有一个长度为 n 的数组 a 和一个长度为 n 的字符串 s。她最多可以将数组切割成 k 块。

定义数组的权值为所有元素的权值之和。对于数组中的第 i 个元素，其权值计算方式为：op(i) \times (a_i + j)
其中：
- op(i) 的值取决于字符串 s 的第 i 个字符：
- 若 s_i = '1'，则 op(i) = 1
- 若 s_i = '0'，则 op(i) = -1
- j 表示 a_i 所在的块的编号（从 1 开始）

小红想要通过合理的切割方式，使得数组的总权值最大。请你帮她计算出可能的最大权值。

输入描述:
第一行包含两个正整数 n 和 k，表示数组的长度和数组最多的块数。
第二行包含 n 个整数 a_1, a_2, ..., a_n，表示数组 a。
第三行包含一个长度为 n 的字符串 s，仅由字符 '0' 和 '1' 组成。
1 \leq k \leq n
2 \leq n \leq 10^5
1 \leq a_i \leq 10^9


输出描述:
输出一个整数，表示数组可能的最大权值。
示例1

输入

4 2
1 2 3 4
1001

输出

1

说明

一种最优的切割方案是将数组切成 [1, 2, 3] 和 [4] 两块。
算法知识视频讲解
开通博客
头像 丨阿伟丨
发表于 2025-09-12 15:58:43
题目链接 REAL739 小红的数组切割 题目描述 小红有一个长度为 的数组 和一个长度为 的字符串 。她最多可以将数组切割成 个连续的块。 数组的总权值为所有元素的权值之和。对于数组中的第 个元素，其权值计算方式为：。其中： 的值取决于字符串 的第 个字符：若 ，则 ；若 ，则 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

贪心 前缀和 排序 阿里云
难度：
1条回答 565浏览

热门推荐

相关试题

小红的数组切割

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号