luogu#P9492. 「SFCOI-3」进行一个拆的解
「SFCOI-3」进行一个拆的解
题目背景
公告:Subtask 0 数据有误,现已更改。
三岁的小明非常不喜欢完整的东西,他甚至连序列都想要拆掉。
题目描述
给定序列 ,小明想要把它拆成两个子段 ,即 和 。
由于小明强迫症很严重,他不希望对于这两个子段,其中一个是另一个的 子序列,换句话说,他不希望其中一个子段可以通过删掉若干(可能为 )个元素变成另一个。
在父母出门的时候,小明终于找到了把序列拆开的机会!所以,他想知道,是否存在一种拆解的方式满足:任意一个子段都不是另一个子段的子序列。
输入格式
第一行一个整数 ,表示小明总共要拆解 个序列。接下来 行,每行描述一个序列:
- 每行第一个整数 ,表示序列长度;
- 接下来 个整数,依次代表序列中每一个数。
输出格式
输出共 行。
对于每轮游戏,若存在满足条件的序列,输出 YES
,否则输出 NO
。
2
5 1 2 1 2 1
7 1 2 1 1 2 1 0
NO
YES
提示
样例解释
对于第一个序列,所有拆分方式有:
- 。
- 。
- 。
- 。
从任何地方拆开都是不合法的——较短的那个序列都是另一个序列的子序列。
对于第二个序列,其中一种合理的拆分方式为 。
数据规模与约定
本题采用捆绑测试。
- Subtask 0(15 points):。
- Subtask 1(15 points):,保证数据随机生成。
- Subtask 2(30 points): 为偶数。
- Subtask 3(40 points):无特殊限制。
对于所有数据,,,,。