#P11639. Line Game
Line Game
题目描述
你在玩一个音游。
这个音游可以抽象为一个长度为 的线段。
这个音游有 秒,在前 秒中,第 秒会在 处出现一个集合,这个集合可以用一个可重无序集 来表示,大小为 ,每秒末尾这个集合的位置会增加 。
因为你不会玩,所以你有一个可爱的 bot,它在第 秒位于 ,之后每一秒你都需要选择一个值域区间 ,若这个 bot 所处位置有一个非空的集合 ,那么 bot 会消去 中值域位于 的数,该操作代价为 。除此之外,这个 bot 在每秒的末尾可以选择将自己的位置 。
若有非空的集合到达 处,那么你就失败了。请问在不失败的情况下你最少需要花费多少代价?
输入格式
第一行两个整数 。
接下来 行,每行第一个整数为 ,接下来有 个整数,表示集合 。
输出格式
一行一个整数,表示最小代价。
1 2
4 1 2 6 7
4
提示
设 为集合中元素的值域。
本题采用捆绑测试。
- Subtask#1():;
- Subtask#2():;
- Subtask#3():;
- Subtask#4():;
- Subtask#5():;
- Subtask#6():无特殊限制。
对于 的数据,,,,除 Subtusk#3 外 。