暴力求解

---

Avin is studying series. A series is called “wave” if the following conditions are satisfied:

1. It contains at least two elements;
2. All elements at odd positions are the same;
3. All elements at even positions are the same;
4. Elements at odd positions are NOT the same as the elements at even positions.
   You are given a series with length n. Avin asks you to find the longest “wave” subseries. A subseries is a subsequence of a series.
   Input
   The first line contains two numbers n, c (1 ≤ n ≤ 100, 000, 1 ≤ c ≤ 100). The second line contains n integers whose range is [1, c], which represents the series. It is guaranteed that there is always a “wave” subseries.
   Output
   Print the length of the longest “wave” subseries.
   Sample Input
   5 3
   1 2 1 3 2
   Sample Output
   4

分析

暴力求解枚举的话，复杂度为ncc~~=1e9。但是由于一次只需要关心两个数字，所以如果能记录两个数字的位置，跳过不相干的数字，复杂度就会大大减少，变为 （n/c）cc,约等于1e7，

所以：
1.利用vector存储各个数字在序列出现的位置。
2.枚举。

import java.io.IOException;
import java.util.Scanner;
import java.util.Vector;public class Main{public static void main(String[] args)throws IOException {Scanner sc=new Scanner(System.in);Vector<Integer>[]v=new Vector[101];int [][]dp=new int [101][101];int n,x,c;while(sc.hasNext()) {n=sc.nextInt();c=sc.nextInt();for(int i=0;i<=100;i++) v[i]=new Vector();for(int i=1;i<=n;i++) {x=sc.nextInt();v[x].add(i);}int ans=0;for(int i=1;i<=c;i++) {for(int j=1;j<=c;j++) {if(i==j) continue;int len1=v[i].size(),len2=v[j].size();if(len1==0||len2==0) continue;if(len1+len2<=ans) continue;int x1,x2,now,sum;x1=x2=now=sum=0;while(true) {while(x1<len1&&v[i].get(x1)<now) x1++;if(x1==len1) break;now=v[i].get(x1);sum++;while(x2<len2&&v[j].get(x2)<now) x2++;if(x2==len2) break;now=v[j].get(x2);sum++;}ans=Math.max(ans, sum);}}System.out.println(ans);}}
}

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.util.Vector;public class Main{static int N=(int)1e5+1,n,m,l,r,t,area=0;static int []a,b,sum;
//	static boolean []a;static FastScanner sc = new FastScanner(System.in);// 快读static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));// 快速输出public static void main(String[] args)throws IOException {
//		Scanner sc=new Scanner(System.in);a=new int [N];b=new int [N];int [][]dp=new int [101][101];Vector<Integer>arr[]=new Vector[101];for(int i=0;i<=100;i++) arr[i]=new Vector();//这一个样例开始前都应该重新new一下int x;while(sc.hasNext()) {n=sc.nextInt();int c=sc.nextInt();for(int i=1;i<=n;i++) {a[i]=sc.nextInt();arr[a[i]].add(i);}int ans=0;for(int i=1;i<=c;i++) {for(int j=1;j<=c;j++) {if(j==i) continue;int len1=arr[i].size(),len2=arr[j].size();int x1=0,x2=0,now=0,sum=0;//模拟相交过程while(true) {while(x1<len1&&arr[i].get(x1)<now) {x1++;//找到比当前位置(now)大的。}if(x1==len1) break;now=arr[i].get(x1);//找到第一个比当前坐标大的sum++;while(x2<len2&&arr[j].get(x2)<now) {x2++;}if(x2==len2) break;now=arr[j].get(x2);sum++;}ans=Math.max(ans, sum);}}System.out.println(ans);}}static void a(int n,int []a) {for(int i=1;i<=n;i++) {a[i]=sc.nextInt();}}
}
class FastScanner {BufferedReader br;StringTokenizer st;public FastScanner(InputStream in) {br = new BufferedReader(new InputStreamReader(in), 16384);eat("");}public void eat(String s) {st = new StringTokenizer(s);}public String nextLine() {try {return br.readLine();} catch (IOException e) {return null;}}public boolean hasNext() {while (!st.hasMoreTokens()) {String s = nextLine();if (s == null)return false;eat(s);}return true;}public String next() {hasNext();return st.nextToken();}public int nextInt() {return Integer.parseInt(next());}public double nextDouble() {return Double.parseDouble(next());}
}