#1962. 学习轨迹
学习轨迹
学习轨迹
题目描述
标题: 学习轨迹 - Problem - QOJ.ac
The problem was used in the following contests:
马上就要比赛了,小 D 决定突击学习一些算法。
他要学习的算法共有 n 个,这些算法被依次标号为 1,2,⋯,n。
小 D 根据学习难度以及实用价值等方面,给每个算法定了一个价值。其中,编号为 i 的算法的价值是 wi。
小 D 想要以某种顺序学完所有的这 n 个算法。我们把他学习的顺序可以看做一个 1,2,⋯,n 的排列 p,其中第 i 项 pi 表示第 i 个学习的算法的编号。
小 D 不希望连续学习的算法之间价值差异过大。对于一种学习方案,他定义这种方案的代价为相邻两个学习的算法的价值差之和。形式化地,对于排列 p,我们定义他的权值 w(p) 为:
w(p)=∑i=1n−1|wpi−wpi+1|
但是,小 D 很快发现了一些问题:有的算法之间具有依赖关系,例如学习 LCT 需要先学习 Splay。小 D 把这些算法分成了两类:基础算法和延伸算法。
基础算法共有 m 个,为了方便,小 D 把它们编号为 1,2,⋯,m;延伸算法是剩下的 n−m 个算法,编号为 m+1,m+2,⋯,n。
对于每个延伸算法 i(m+1≤i≤n),该算法会依赖恰好一个基础算法,记作 ui(1≤ui≤m)。即,算法 i 必须要在算法 ui 之后学习。
小 D 想要知道,在所有满足这些依赖关系的学习序列 p 中,w(p) 最小的那一个。
因为小 D 还没开始学这 n 个算法,所以他并不会算。请你帮他求出 w(p) 的最小值,以及一个取到该最小值的排列 p。
输入格式
从标准输入读入数据。
第一行包括两个空格隔开的整数 n,m,分别表示算法的总数,基础算法的个数。
第二行包括 n 个空格隔开的整数,其中第 i 个数 wi 表示算法 i 的价值。
第三行包括 n−m 个空格隔开的整数,其中第 i 个数 um+i 表示延伸算法 m+i 依赖的算法的编号。
输出格式
输出到标准输出。
第一行包括一个整数,表示 w(p) 的最小值。
第二行包括 n 个空格隔开的整数,其中第 i 个数 pi 表示最优解中,第 i 个学习的算法编号。
可以证明,在题目的限制下,小 D 一定可以学完所有的算法,即合法的 p 一定存在。如果有多个使 w(p) 取最小值的合法的 p,你可以输出其中任意一个。
样例数据
样例输入
6 2
1 3 2 4 5 6
2 2 1 1
样例输出
7
2 3 1 4 5 6
评分方式
对于每组测试数据,若你输出的 w(p) 是正确的,则你可以得到该测试点 60% 的分数。
此外,若你输出的排列 p 是一组可以使 w(p) 取最小值的合法方案,则你可以得到该测试点剩余 40% 的分数。
请注意,即使对于某些测试点,你可能只想要得到部分分,但是你仍然需要严格按照输出格式进行输出。
子任务
对于所有测试数据,1≤n≤106,1≤m≤n,1≤wi≤1012,1≤ui≤m(m+1≤i≤n)。
本题共 7 个子任务,对于每个子任务,你的得分为你在该子任务中所有测试数据上得分的最低者。
各子任务的特殊限制见下表:
子任务编号 分值 n 特殊限制 1 5 ≤105 m=n 2 5 ≤10 无 3 10 ≤20 4 10 ≤105 ∀1≤i≤n,wi≤10 5 30 ≤5000 无 6 20 ≤105 7 20 ≤106
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
6 2
1 3 2 4 5 6
2 2 1 1
7
2 3 1 4 5 6