首页 > 试题广场 >

小红的双排列删除得分

[编程题]小红的双排列删除得分
  • 热度指数：601 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 1024M，其他语言2048M
  • 算法知识视频讲解
\hspace{15pt}小红拿到了一个长为 2\times n 的双排列 \{a_{1},a_{2},...,a_{2\times n}\} 。
\hspace{15pt}小芳能帮他进行任意次如下操作：
\hspace{23pt}\bullet选择一个首尾元素相等的区间 \left[l,r\right]\left(1 \leqq l < r \leqq 2 \times n;\ a_{l} = a_{r}\right) ，将 a_{l},a_{l+ 1},...,a_{r} 这段元素删除，并将其余元素按现有顺序拼接起来，同时小红将获得 \sum\limits_{i = l}^{r}{a_{i}} 分。 
\hspace{15pt}请你帮小红求出可能的最高得分。

【名词解释】
\hspace{15pt}双排列：长度为 2\times n 的双排列为两个长度为 n 的排列打乱顺序后得到的数组。
\hspace{15pt}排列：长度为 n 的排列是由 1,2,\dots,n 这 n 个整数、按任意顺序组成的数组（每个整数均恰好出现一次）。例如，\{2,3,1,5,4\} 是一个长度为 5 的排列，而 \{1,2,2\} 和 \{1,3,4\} 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

输入描述:
\hspace{15pt}第一行输入一个整数 n\left(1\leqq n \leqq 2\times 10^{5}\right)。
\hspace{15pt}第二行输入 2 \times n 个整数 a_{1},a_{2},...,a_{2\times n}\left(1 \leqq a_{i} \leqq n\right)，表示双排列的元素。保证其是一个合法的双排列。


输出描述:
\hspace{15pt}输出一个整数，代表最高得分。
示例1

输入

2
1 2 1 2

输出

5
算法知识视频讲解
添加回答
精致的熊熊在努力存钱头像 精致的熊熊在努力存钱
n = int(input())
li = list(map(int,input().split()))
qzh = [0] * 2 * n
qzh[0] = li[0]
for i in range(1,2*n):
    qzh[i] = qzh[i-1] + li[i]
dp  = [0] * 2 * n
dic = {li[0]:0}
for i in range(1,2*n):
    cur = li[i]
    if cur not in dic.keys():
        dic[cur] = i
        dp[i] = dp[i-1]
    else:
        l = dic[cur]
        r = i
        if l == 0:
            dp[i] = max(dp[i-1],qzh[r])
        else:
            dp[i] = max(dp[i-1],qzh[r]-qzh[l-1]+dp[l-1])
print(dp[-1])
发表于 2026-02-11 22:31:01 回复(0)
提交观点

问题信息

难度：
1条回答 65浏览

热门推荐

相关试题

小红的双排列删除得分

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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