#P11727. [JOIG 2025] 神経衰弱 2 / Pair Matching 2
[JOIG 2025] 神経衰弱 2 / Pair Matching 2
题目描述
有 张卡牌从左到右依次放在桌子上,编号为 ,卡牌 上写有整数 。对于 ,存在恰好两张卡牌上写的整数为 。
海狸比太郎决定用这些卡牌玩一个叫做“神经衰弱”的游戏;该游戏的流程如下:
- 依次考虑卡牌 :
- 比太郎决定是否拿起这张卡牌:如果他决定拿起,那么依次进行以下的步骤 2 至步骤 5;如果他决定不拿起(跳过该卡牌),则跳过以下的步骤;
- 如果比太郎的手中持有一张写有 的卡牌,那么该卡牌和卡牌 同时消失,他获得 分;
- 如果比太郎左手中有一张卡牌,那么他将其丢弃;
- 如果比太郎右手中有一张卡牌,那么他将其转移到左手;
- 如果卡牌 没有在步骤 2 中消失,那么他将其放在右手中。
通过上面的流程,每次得到的分数之和即为比太郎的最终得分。
请求出比太郎能获得的最大得分。
输入格式
第一行输入一个整数 。
第二行输入 个整数 。
第三行输入 个整数 。
输出格式
输出一行一个整数,表示最大得分。
3
1 2 3 1 2 3
5 2 8
13
4
1 2 1 2 3 4 4 3
39 62 55 21
156
10
7 2 5 8 4 10 8 2 7 5 6 3 4 1 10 9 9 1 6 3
185163245 734376902 849123714 97860221 844860642 689054872 471545587 607735137 664633003 831663829
3117416130
15
4 3 8 3 10 15 14 1 12 4 13 1 6 7 10 15 2 8 12 2 9 11 11 13 5 9 14 5 6 7
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
6
提示
【样例解释 #1】
比太郎可以通过以下流程获得分数 :
- 拿起卡牌 ,该卡牌上面写着 ;由于比太郎没有其他写着 的纸牌,所以他将其放在右手中;
- 跳过卡牌 ;
- 拿起卡牌 ,该卡牌上面写着 ;由于比太郎没有其他写着 的纸牌,所以卡牌 从右手转移到了左手,他将卡牌 放在右手中;
- 拿起卡牌 ,该卡牌上面写着 ;由于卡牌 上也写着 ,所以两张牌都消失了,他获得 分,卡牌 则从右手转移到了左手;
- 跳过卡牌 ;
- 拿起卡牌 ,该卡牌上面写着 ;由于卡牌 上也写着 ,所以两张牌都消失了,他获得 分,此时他两只手上都没有任何卡牌了。
可以证明这是最优的。
该样例满足子任务 的限制。
【样例解释 #2】
比太郎可以通过拿起卡牌 来获得分数 。可以证明这是最优的。
该样例满足子任务 的限制。
【样例解释 #3】
该样例满足子任务 的限制。
【样例解释 #4】
该样例满足子任务 的限制。
【数据范围】
- ;
- 中,对于 , 正好出现两次;
- 。
【子任务】
- ( 分),;
- ( 分);
- ( 分);
- ( 分);
- ( 分)
- ( 分);
- ( 分),;
- ( 分);
- ( 分)无附加限制。