×

计蒜客

  1. 题库
  2. 百度AI小课堂-上升子序列(困难)
  3. 问答
  • 16.55%
  • 524288K

题目背景

​$9102$ 年 $9$ 月 $4$ 日,百度在 X 市 XX 中学举办的第一场 AI 知识小课堂大获好评!同学们对矩阵的掌握非常棒。

今天的 AI 知识小课堂的第四场开讲啦。本场 AI 知识小课堂老师教授的是数组的相关知识---上升子序列。

题目描述

给一个长度为 $n$ 的数组 $a$ 。试将其划分为两个严格上升子序列,并使其长度差最小。

输入格式

输入包含多组数据。

数据的第一行为一个正整数 $T$ ,表示数据组数。

每组数据包括两行:

第一行包括一个正整数 $n$ 。

第二行包括一个长度为 $n$ 的数组 $a$。

输出格式

对于每组数据输出一行一个整数,表示两个子序列的最小长度差。若不存在划分方案则输出 $-1$ 。

数据范围

$ T \le 10 , n \le 10^5 , a_i \in [ 0 , 2^{30} ]$ 。

特殊限制及约定:合法的划分方案数不超过 $10^{18}$ 。

输出时每行末尾的多余空格,不影响答案正确性

样例输入

2
7
1 4 2 5 6 3 7
5
5 4 3 2 1

样例输出

1
-1

想挑战这道题吗

  • main.c