P4437 [HNOI/AHOI2018]排列

    • 144通过
    • 656提交
  • 题目提供者 Kelin
  • 评测方式 云端评测
  • 标签 贪心 各省省选 2018 安徽 湖南
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    给定 $n$ 个整数 $a_1, a_2, \dots, a_n, 0 \le ai \le n$,以及 $n$ 个整数 $w_1, w_2, \dots, w_n$。称 $a_1, a_2, \dots, a_n$的 一个排列 $a_{p[1]}, a_{p[2]}, \dots, a{p[n]}$为 $a_1, a_2, \dots, a_n$的一个合法排列,当且仅当该排列满足:对于任意 的 $k$ 和任意的 $j$,如果 $j \le k$,那么 $a_{p[j]}$不等于 $p[k]$。(换句话说就是:对于任意的 $k$ 和任意的 $j$,如果 $p[k]$等于 $ap[j]$,那么 $k<j$。)定义这个合法排列的权值为 $w_{p[1]} + 2w_{p[2]} + \dots + nw_{p[n]}$。

    你 需要求出在所有合法排列中的最大权值。如果不存在合法排列,输出$-1$。

    样例解释中给出了合法排列和非法排列的实例。

    输入输出格式

    输入格式:

    第一行一个整数 n。 接下来一行 n 个整数,表示$a_1, a_2, \dots, a_n$。 接下来一行n 个整数,表示 $w_1, w_2, \dots, w_n$。

    输出格式:

    输出一个整数表示答案

    输入输出样例

    输入样例#1: 复制
    3 
    0 1 1 
    5 7 3 
    输出样例#1: 复制
    32
    输入样例#2: 复制
    3 
    2 3 1 
    1 2 3 
    输出样例#2: 复制
    -1
    输入样例#3: 复制
    10 
    6 6 10 1 7 0 0 1 7 7 
    16 3 10 20 5 14 17 17 16 13 
    输出样例#3: 复制
    809

    说明

    【样例解释 1】

    对于 a1=0,a2=1,a3=1,其排列有

    a1=0,a2=1,a3=1,是合法排列,排列的权值是 1*5+2*7+3*3=28;
    a2=1,a1=0,a3=1,是非法排列,因为 ap[1]等于 p[2];
    a1=0,a3=1,a2=1,是合法排列,排列的权值是 1*5+2*3+3*7=32;
    a3=1,a1=0,a2=1,是非法排列,因为 ap[1]等于 p[2];
    a2=1,a3=1,a1=0,是非法排列,因为 ap[1]等于 p[3];
    a3=1,a2=1,a1=0,是非法排列,因为 ap[1]等于 p[3]。

    因此该题输出最大权值 32。

    【样例解释 2】

    对于 a1=2,a2=3,a3=1,其排列有:

    a1=2,a2=3,a3=1,是非法排列,因为 ap[1]等于 p[2];
    a2=3,a1=2,a3=1,是非法排列,因为 ap[1]等于 p[3];
    a1=2,a3=1,a2=3,是非法排列,因为 ap[1]等于 p[3];
    a3=1,a1=2,a2=3,是非法排列,因为 ap[2]等于 p[3];
    a2=3,a3=1,a1=2,是非法排列,因为 ap[2]等于 p[3];
    a3=1,a2=3,a1=2,是非法排列,因为 ap[1]等于 p[3]。

    因此该题没有合法排列。

    【数据范围】

    对于前20% 的数据,1≤n≤ 10。
    对于前40% 的数据,1≤n ≤ 15。
    对于前60% 的数据,1≤n ≤1000。
    对于前80% 的数据,1≤n ≤100000。
    对于100% 的数据,1≤n ≤ 500000,0 ≤ ai ≤ n,1 ≤ wi ≤ 10^9 ,所有wi的和不超过 1.5×10^13。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。