codeforces 27 C. Unordered Subsequence

http://codeforces.com/contest/27/problem/C
题意:给出一个序列,问是否存在一个disordered的子序列。。输出长度并输出组成子序列的下表(1..n)。如果有多组,输出任意一组。
disordered的意思是。。升序或者降序(不严格也可以)之外的情况。
思路: 首先我们可以知道,我们要找的子序列至少需要三个点。因为两个点怎么看都是有序的。而如果有k个点(k>3)组成的子序列存在。。那么机智得去掉其中一些点,可以只剩三个 ,同样满足题意。所以我们只需要找到三个点即可。如果把点以下标为横坐标,值为纵坐标花在坐标系上,就是找一个v型或者倒v型的三个点。

第二,我们可以将找三个点的问题转化成用第一个点+找两个点的问题。我们可以证明,如果解存在,那么包含第一个点的解也一定存在。我们可以用反证法证明,如果我们选了第1个点,然后从第2个点到第n个点。。我们找不到两个点与第一个点构成一个v型,那么整个序列一定是升序或者降序,无解,与前提矛盾。

需要注意的,判断方向的时候我用了乘,可能会爆int,记得用long long 

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz