首页 > 专题系列 > Java解POJ > POJ 3298 Antimonotonicity [解题报告] Java
2013
11-12

POJ 3298 Antimonotonicity [解题报告] Java

Antimonotonicity

问题描述 :

I have a sequence Fred of length n comprised of integers between 1 and n inclusive. The elements of Fred are pairwise distinct. I want to find a subsequence Mary of Fred that is as long as possible and has the property that:

Mary0 > Mary1 < Mary2 > Mary3 < …

输入:

The first line of input will contain a single integer T expressed in decimal with no leading zeroes. T will be at most 50. T test cases will follow.

Each test case is contained on a single line. A line describing a test case is formatted as follows:

n Fred0 Fred1 Fred2Fredn-1.

where n and each element of Fred is an integer expressed in decimal with no leading zeroes. No line will have leading or trailing whitespace, and two adjacent integers on the same line will be separated by a single space. n will be at most 30000.

输出:

For each test case, output a single integer followed by a newline — the length of the longest subsequence Mary of Fred with the desired properties.

样例输入:

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

样例输出:

1
2
5
3

解题代码:

// author:M.J
import java.util.*;
import java.io.*;
public class Main{
 public static void main(String[] args){
  Scanner in = new Scanner(new BufferedInputStream(System.in));
	int T = in.nextInt();
	while(T > 0){
		T--;
		int n = in.nextInt();
		int k = in.nextInt();
		n--;
		int curr = k;
		int flag = 0;
		int ans = 1;
		while(n > 0){
			n--;
			k = in.nextInt();
			if(flag%2==0 && curr < k)
				curr = k;
			else if(flag%2==1 && curr > k)
				curr = k;
			if(flag%2==0 && k < curr){
				flag ++;
				ans ++;
				curr = k;
			}
			else if(flag%2==1 && k > curr){
				flag ++;
				ans ++;
				curr = k;
			}
		}
		System.out.println(ans);
	}
   }
}

  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  2. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。