#P3180. [Coci2012]ograda
[Coci2012]ograda
[COCI 2011/2012 #4] OGRADA
题目描述
Mirko 村里的围栏都由 块高度各不相同的木板排成。围栏的美观度是每对相邻木板的高度差的绝对值之和。
Mirko 买了 块木板,想把围栏排得和 Slavko 的围栏相似,同时使美观度尽可能大。若两道围栏每对相邻木板的升降关系相同,就称它们相似。也就是说,对每个 ,若 Slavko 围栏的第 块木板低于第 块,Mirko 的围栏也要在此处上升。若 Slavko 的围栏在此处下降,Mirko 的围栏也要下降。
给出 Slavko 围栏从左到右的木板高度 ,以及 Mirko 买来的木板高度 。求 Mirko 围栏的最大美观度以及一种达到这个值的相似排列。
输入格式
第一行包含整数 ()。
第二行包含 个互不相同的正整数 。
第三行包含 个互不相同的正整数 。
保证每个高度都小于 。
输出格式
第一行输出最大美观度。
第二行输出 个整数,表示 Mirko 的木板从左到右的排列。如有多种最优排列,可以输出任意一种。
4
5 7 4 9
1 2 3 4
7
2 4 1 3
10
9 5 1 2 6 7 4 18 20 12
10 40 20 30 50 70 80 100 1000 500
3010
100 80 10 40 50 1000 20 70 500 30
样例 1 解释
| 木板排列 | 美观度 |
|---|---|
原题评分
在原比赛中,若第一行的美观度正确而第二行缺失或错误,可获该测试用例分值的 。