admin管理员组

文章数量:814285

COJ

I. 成群的触手

Time Limit: 1000ms Memory Limit: 65536KB 饭团学长终于成功的约了漂亮的大姐姐,但是漂亮大姐姐来约会的路上要经过一片沼泽地,为了能让漂亮大姐姐顺利渡过沼泽,饭团学长发现沼泽地里生长着成群的触手,所以决定利用触手搭桥。 但是触手们也有自己的脾气,他们已经排成了一序列,并且每个触手有着不同的高度 ai ai。为了表示浪漫,学长决定从中选出m个触手,使选出的触手满足长度从低到高再从高到低,且选出的相邻触手长度不等(例如:1 2 3 2 1是长度为5浪漫的序列,1 2 3 则不是浪漫的序列,同理3 2 1也不是浪漫的序列 。注意1 2 1 2也不是浪漫的序列,因为其长度是从低到高再到低再到高,学长认为这会让漂亮姐姐觉得不舒服)。但是学长一心只想着漂亮大姐姐无心写代码,请你帮助下颓废的学长吧。

Input

第一行一个数 T T,代表有 (T<100) (T<100)个样例; 每个样例的第一行输入两个整数 n n, m m用空格分隔, n(n<103) n(n<103)代表触手的数量, m m( m<n m<n)代表希望的浪漫序列长度。 接下来一行 有 n n 个数 ai(ai<109) ai(ai<109),用空格分隔 。

Output

如果能有这样一个长度为 m m的浪漫序列,输出YES。否则输出NO。

Sample Input

3
3 3
1 2 3
3 3
3 2 1
5 4
1 2 3 2 1

Sample Output

NO
NO
YES

Hint

例如,第三组样例,m=4,可构成题目描述中的“从矮到高再从高到矮的子序列”的有:(1,2,1),(1,3,2),(1,3,1),(2,3,2),(2,3,1),(1,2,3,2),(1,2,3,1),(1,3,2,1),(2,3,2,1),(1,2,3,2,1) 在这些序列中显然有长度为4的,所以输出“YES”。

















































双向最长严格递增子序列,双向dp,这里给出O(nlogn)的算法,因为直接dp是O(n^2),这里用dp当然能过,因为最长也就1000个点,但如果最长是10W个点这里用数组模拟栈+贪心的优势就将体现出来。

关于这种方法求LIS(Longest Increasing Subsequence)可以参照我的另一篇博客:

关键是这里用了d数组去记录,d[i]表示以a[i]为终点的最长增加子序列的长度,这样正反一扫,最后能找到一个d1[i] + d2[i] - 1 >= m 则满足情况 交点算了两次故减一。


#include <bits/stdc++.h>using namespace std;
const int MAXN = 1000 + 7;
const int inf = 1e9 + 7;
int n, m, a[MAXN], d1[MAXN], d2[MAXN], stimulate_stack1[MAXN], stimulate_stack2[MAXN];int main()
{int t;scanf("%d", &t);while (t--){bool flag = false;memset(a, 0, sizeof(a));memset(d1, 0, sizeof(d1));memset(d2, 0, sizeof(d2));scanf("%d%d", &n, &m);for (int i = 1; i <= n; ++i){scanf("%d", &a[i]);stimulate_stack1[i] = stimulate_stack2[i] =  inf;}for (int i = 1; i <= n; ++i){int k1 = lower_bound(stimulate_stack1 + 1, stimulate_stack1 + n + 1, a[i]) - stimulate_stack1;d1[i] = k1;stimulate_stack1[k1] = a[i];int k2 = lower_bound(stimulate_stack2 + 1, stimulate_stack2 + n + 1, a[n-i+1]) - stimulate_stack2;d2[n-i+1] = k2;stimulate_stack2[k2] = a[n-i+1];}for(int i = 1; i <= n; ++i){if(d1[i] + d2[i] - 1 >= m && (d1[i] > 1 && d2[i] > 1)){flag = true;break;}}if(flag)cout << "YES" << endl;elsecout << "NO" << endl;}return 0;
}



本文标签: COJ