首页 > 试题广场 >

支配权值划分

[编程题]支配权值划分

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

$\hspace{15pt}$ 给定一个数组 $t$ ，定义任意数 $x$ 在 $t$ 中的出现次数为 $\mathrm{cnt}(x)$ 。称 $t$ 被 $v$ 支配，当且仅当对任意 $v'$ 有 $\mathrm{cnt}(v)\ge \mathrm{cnt}(v')$ ；若出现次数相同，则取数值最大的那个 $v$ 。定义数组 $t$ 的权值为 $v \times |t|$ （其中 $|t|$ 为 $t$ 的长度）。

$\hspace{15pt}$ 现在给定一个长度为 $n$ 的数组 $a_1,a_2,\dots,a_n$ ，你需要将其划分为若干个非空连续子数组，使得各子数组权值之和最小，输出该最小值。

$\hspace{15pt}$ 【子数组】子数组为原数组中任意一个连续且非空的元素区间。

输入描述:

输入包含多组测试数据。第一行包含整数  表示测试组数。每组数据描述如下： 
第一行包含一个整数 ； 
第二行包含  个整数，表示数组 。 
保证所有测试中  的总和不超过 。

输出描述:

对于每组测试数据，输出一行一个整数，表示将数组划分为若干非空连续子数组后，权值之和的最小值。

示例1

输入

输出

8
15
10

说明

样例一：一种最优划分为 ，权值分别为 ，总和 。 
样例二：任意划分总和均为 。 
样例三：将其划分为单点 ，总和 。

算法知识视频讲解

爱吃的杰克在许愿

动态规划，一边求权值一边更新dp

def minCost(seq):
    n = len(seq)
    valSet = set(seq)
    valDict = {val: i for i, val in enumerate(valSet)}
    m = len(valSet)
    INF = 10**19
    dp = [INF] * (n + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        freqArr = [0] * m
        bestVal = weight = 0
        for j in range(i - 1, -1, -1):
            val = seq[j]
            idx = valDict[val]
            freq = freqArr[idx] + 1
            freqArr[idx] = freq
            if freq > weight&nbs***bsp;(freq == weight and val > bestVal):
                bestVal, weight = val, freq
            cost = bestVal * (i - j)
            dp[i] = min(dp[i], dp[j] + cost)
    return dp[n]

编辑于 2026-04-13 14:43:30 回复(0)

提交观点

问题信息

难度：

1条回答 11收藏 107浏览

支配权值划分

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题