安娜与朋友布鲁诺玩过卡牌游戏,但两人对双人游戏感到厌倦,于是她设计了一款可单人游玩的卡牌游戏。
游戏开始时,有 张不同颜色的卡牌排成一行,每张卡牌上写有一个整数。每张卡牌的颜色用整数表示,每张卡牌也有一个固定的价值。在游戏开始时,从队列前端起第 张卡牌()的颜色为 ,写在上面的整数为 ,其价值为 。
游戏通过从卡牌序列中逐张选取卡牌并将其加入牌堆来进行。初始时牌堆为空,从该状态开始,安娜重复以下操作:
- 操作:从卡牌序列的前端选择第 1 张或第 3 张卡牌。但若操作前牌堆中已有卡牌,则只能从序列中选择一张与牌堆最上方卡牌颜色相同,或写有相同整数的卡牌。选出的卡牌从序列中移除,并添加到牌堆的最上方。
当无法再选择任何卡牌时,游戏结束。游戏结束时,牌堆中所有卡牌的价值之和即为安娜的得分。
问:在此游戏中,安娜能够获得的最大得分是多少?
题目
给定游戏开始时排列的卡牌信息,编写程序求出安娜在该游戏中可能获得的最大得分。