首页 > 试题广场 >

小红的数组切割

[编程题]小红的数组切割

热度指数：158 时间限制：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 开始）

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

输入描述:

第一行包含两个正整数  和 ，表示数组的长度和数组最多的块数。
第二行包含  个整数 ，表示数组 。
第三行包含一个长度为  的字符串 ，仅由字符 '0' 和 '1' 组成。

输出描述:

输出一个整数，表示数组可能的最大权值。

示例1

输入

4 2
1 2 3 4
1001

输出

说明

一种最优的切割方案是将数组切成 [1, 2, 3] 和 [4] 两块。

算法知识视频讲解

geniecyy

n,k=list(map(int,input().strip().split()))
a=list(map(int,input().strip().split()))
s=input().strip()
dp=[[-float("inf")]*(1+k) for _ in range(1+n)]
dp[0][0]=0
weight=[0]*n
for i in range(n):
    if s[i]=='0':
        weight[i]=-1
    else:
        weight[i]=1


presum=[0]*(n+1)
opsum=[0]*(n+1)
ans=-float("inf")
for i in range(1,n+1):
    presum[i]=presum[i-1]+weight[i-1]*a[i-1]
for i in range(1,n+1):
    opsum[i]=opsum[i-1]+weight[i-1]

for i in range(1,n+1):
    for j in range(1,min(i,k)+1):
        for t in range(0,i):

            dp[i][j]=max(dp[i][j],dp[t][j-1]+(opsum[i]-opsum[t])*j+presum[i]-presum[t])
for j in range(1,min(n,k)+1):
    ans=max(ans,dp[-1][j])

print(ans)

最直观的dp+前缀和内存爆炸

发表于 2025-09-11 15:18:20 回复(0)