PAT (Top Level) Practise 1017 The Best Peak Shape (35)

1017. The Best Peak Shape (35)

時間限制

1000 ms

記憶體限制

65536 kB

代碼長度限制

8000 B

判題程式

Standard

作者

CHEN, Yue

In many research areas, one important target of analyzing data is to find the best "peak shape" out of a huge amount of raw data full of noises. A "peak shape" of length L is an ordered sequence of L numbers { D1, ..., DL } satisfying that there exists an index i (1 < i < L) such that D1 < ... < Di-1 < Di > Di+1 > ... > DL.

Now given N input numbers ordered by their indices, you may remove some of them to keep the rest of the numbers in a peak shape. The best peak shape is the longest sub-sequence that forms a peak shape. If there is a tie, then the most symmetric (meaning that the difference of the lengths of the increasing and the decreasing sub-sequences is minimized) one will be chosen.

Input Specification:

Each input file contains one test case. For each case, the first line gives an integer N (3 <= N <= 104). Then N integers are given in the next line, separated by spaces. All the integers are in [-10000, 10000].

Output Specification:

For each case, print in a line the length of the best peak shape, the index (starts from 1) and the value of the peak number. If the solution does not exist, simply print "No peak shape" in a line. The judge's input guarantees the uniqueness of the output.

Sample Input 1:

20
1 3 0 8 5 -2 29 20 20 4 10 4 7 25 18 6 17 16 2 -1      

Sample Output 1:

10 14 25      

Sample Input 2:

5
-1 3 8 10 20      

Sample Output 2:

No peak shape

本場頂級壓軸題,然後卻沒什麼難度。

給出n個數字，要求找出一個序列滿足先上升再下降（嚴格的），求最長的長度，并且同長度要求左右長度差最小。

其實就是求最長上升子序列，對于一個位置i，我們可以從前往後求出以i為結尾的最長上升子序列的長度，同樣可以從後往前再求一遍。

這樣兩邊加起來減一就是這個點的答案，然後在比較一下那個比較優就行了。求最長上升什麼的可以用樹狀數組或者二分。

#include<map> 
#include<set>
#include<ctime>  
#include<cmath>      
#include<queue>   
#include<string>  
#include<vector>  
#include<cstdio>      
#include<cstring>    
#include<iostream>  
#include<algorithm>      
#include<functional>  
using namespace std;
#define ms(x,y) memset(x,y,sizeof(x))      
#define rep(i,j,k) for(int i=j;i<=k;i++)      
#define per(i,j,k) for(int i=j;i>=k;i--)      
#define loop(i,j,k) for (int i=j;i!=-1;i=k[i])      
#define inone(x) scanf("%d",&x)      
#define intwo(x,y) scanf("%d%d",&x,&y)      
#define inthr(x,y,z) scanf("%d%d%d",&x,&y,&z)    
#define infou(x,y,z,p) scanf("%d%d%d%d",&x,&y,&z,&p)   
#define lson x<<1,l,mid  
#define rson x<<1|1,mid+1,r  
#define mp(i,j) make_pair(i,j)  
#define ft first  
#define sd second  
typedef long long LL;
typedef pair<int, int> pii;
const int low(int x) { return x&-x; }
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int N = 3e5 + 10;
const int M = 1e4 + 1;
const double eps = 1e-10;
int n, a[N], l[N], r[N], f[N];

int get(int x) { int res = 0; for (int i = x; i; i -= low(i)) res = max(res, f[i]); return res; }

void add(int x, int y) { for (int i = x; i < N; i += low(i)) f[i] = max(f[i], y); }

int main()
{
  inone(n);
  rep(i, 1, n) inone(a[i]), a[i] += M;
  rep(i, 1, n)
  {
    l[i] = get(a[i] - 1) + 1;
    add(a[i], l[i]);
  }
  ms(f, 0);
  per(i, n, 1)
  {
    r[i] = get(a[i] - 1) + 1;
    add(a[i], r[i]);
  }
  int ans = 0, index = 0, dis = 0;
  rep(i, 1, n)
  {
    if (l[i] < 2 || r[i] < 2) continue;
    if (ans < l[i] + r[i] - 1)
    {
      ans = l[i] + r[i] - 1;
      index = i; dis = abs(l[i] - r[i]);
    }
    else if (ans == l[i] + r[i] - 1 && dis > abs(l[i] - r[i]))
    {
      index = i; dis = abs(l[i] - r[i]);
    }
  }
  if (!ans) puts("No peak shape");
  else printf("%d %d %d\n", ans, index, a[index] - M);
  return 0;
}