#P18092. Deletion Game
Deletion Game
Deletion Game
题目描述
有一个长度为 的整数序列 ,第 个元素的权重为 。
先选择正整数 ,把序列及其权重一起复制成 份并首尾拼接。随后可以进行任意次(也可以零次)消除操作:
选择当前序列中的两个下标 ,要求两处元素值相同。删除第 至第 个元素及对应权重,保留第 个元素;剩余元素按原顺序重新紧密排列。
求剩余元素权重总和的最小值,并求达到这一最小值所需的最小副本数 。两个目标按先权重总和、后副本数的顺序优化。
输入格式
第一行一个整数 。第二行 个整数 。第三行 个整数 。
输出格式
输出一行两个整数,依次为最小权重总和和最小副本数。
数据范围
。
样例 1
输入
6
1 1 4 5 1 4
1 9 1 9 8 10
输出
2 1