题目描述(ID:12219)
标题: 接竹竿
标签: 动态规划
详情: 一天,小哼和小哈在玩扑克牌。他们玩的是一种叫做“接竹竿”的游戏。
游戏规则是:一共有n 张牌,每张牌上有一个花色c 和一个点数v ,花色不超过k种。将这些牌依次放入一列牌的末端。若放入之前这列牌中已有与这张牌花色相同的牌,你可以选择将这张牌和任意一张花色相同的牌之间的所有牌全部取出队列(包括这两张牌本身),并得到与取出的所有牌点数和相同的分数。现在已知小哈把这n 张牌放入队列的顺序,求他最多能得多少分。
输入顺序即为小哈放入队列的顺序。即,ci 表示第 i 张放入的牌的花色,vi 表示第 i 张放入的牌的点数。
请注意,如果你知道类似的纸牌游戏,请尤其仔细地阅读规则,以免因为理解题意错误而出现不必要的问题。

【数据范围与满足性质表】:含义见提示
输入格式:
第一行两个整数 n,k。
第二行,n 个整数 c1,c2,...,cn 表示花色,满足 1≤ci≤k。
第三行,n 个整数 v1,v2,...,vn 表示点数。
输出格式:
输出一行一个整数,表示最多能得到的分数。
提示: 对于100%的数据,1≤n≤10^6,1≤k≤10^6,1≤vi≤10^9。
具体测试点与对应分值、数据范围与满足的特殊性质见上表。
样例:

输入

7 3
1 2 1 2 3 2 3
1 2 1 2 3 2 3

输出

13

解释

第 1 步,向队列加入 1。现在的队列:1
第 2 步,向队列加入 2。现在的队列:1,2
第 3 步,向队列加入 1。现在的队列:1,2,1
第 4 步,向队列加入 2,取出 2,1,2。现在的队列:1
第 5 步,向队列加入 3。现在的队列:1,3
第 6 步,向队列加入 2。现在的队列:1,3,2
第 7 步,向队列加入 3,取出 3,2,3。现在的队列:1

输入

18 5
5 2 3 5 1 3 5 2 1 4 2 4 5 4 1 1 1 5
8 2 7 6 10 8 10 9 10 2 4 7 7 7 7 9 7 3

输出

123
登录并解答