#P18899. [2026多校联测]双轨灯幕
[2026多校联测]双轨灯幕
题目描述
夜市广场上安装了一面双轨灯幕。灯光设计师准备将节目分批播放:每批使用一条亮度递增的轨道和一条亮度递减的轨道,两条轨道可以交错播放,但全部节目的原定顺序不能改变。
共有 个节目,按编号 的顺序播放。第 个节目的亮度为 ,其中 是 至 的一个排列。
设计师需要把全部节目按顺序划分成若干个非空的连续批次,每个节目恰好属于一个批次。对每个批次,需要把其中每个节目恰好分配给一条轨道,使分给向上轨的节目按原顺序组成严格递增序列,分给向下轨的节目按原顺序组成严格递减序列。允许某条轨道在一批中不播放节目;空序列和只含一个节目的序列均满足相应的单调性要求。批次结束后,两条轨道都会复位,下一批的亮度不受上一批影响。
若一个批次的第一个节目编号为 ,本批需要支付 枚月币的启动费用,与本批包含多少个节目无关。全部批次费用相加,就是总费用。
请求出最低总费用,以及达到最低总费用的合法分批方式数量。仅对方式数量取模,模数为 。
两种方式不同,当且仅当它们的批次分界位置不同。同一批次即使有多种轨道分配方式,也不重复计数。
输入格式
第一行一个整数 。
第二行 个整数 。
第三行 个整数 。
输出格式
输出一行两个整数:最低总费用,以及最优分批方式数量对 取模的结果。最低总费用本身不取模。
样例 1 输入
4
2 1 4 3
5 2 1 4
样例 1 输出
6 1
样例 1 解释
四个节目不能同时放在一个批次中:亮度 不能都上向上轨,亮度 也不能都上向上轨,因此向下轨至少要取前一对和后一对中的各一个;而前一对的任意亮度都小于后一对,无法严格递减。
在第 个节目后分批,得到 和 ,费用为 ,两批都可以全部放在向下轨。其他分界方式没有同样低的费用,故答案为 。
样例 2 输入
5
1 2 3 4 5
7 0 2 0 0
样例 2 输出
7 8
样例 2 解释
整个排列严格递增,任意批次都合法。第一个批次必须支付 枚月币;第 个节目均可以免费另开一批,每个位置可选可不选,共有 种最低费用方案。
样例 3
见下发材料中的 ribbon/3.in 和 ribbon/3.ans。这是接近完整规模的附件,不在题面中展开。
子任务
对于所有测试数据,保证:, 是 至 的排列,。
各子任务独立整组计分,通过该组全部测试点才能得到该组分数;各组无依赖关系。
| 子任务 | 分值 | 额外约束 |
|---|---|---|
| 1 | 20 | |
| 2 | ||
| 3 | 严格递增或严格递减 | |
| 4 | 40 | 无额外约束 |