【鏈接】 我是鏈接,點我呀:)
【題意】
題意
【題解】
設f[i]表示i作為序列的最后一個數字,最長的連續序列的長度。
用f[i]和f[i-1]+1來轉移即可
codeforces官網， 【代碼】
import java.io.*;
import java.util.*;public class Main {static InputReader in;static PrintWriter out;public static void main(String[] args) throws IOException{//InputStream ins = new FileInputStream("E:\\rush.txt");InputStream ins = System.in;in = new InputReader(ins);out = new PrintWriter(System.out);//code start from herenew Task().solve(in, out);out.close();}static int N = (int)2e5;static class Task{int n;HashMap<Integer,Integer> dic = new HashMap<Integer,Integer>();int a[] = new int[N+10];ArrayList<Integer> v = new ArrayList<Integer>();public void solve(InputReader in,PrintWriter out) {n = in.nextInt();int len = 0,idx = -1;for (int i = 1;i <= n;i++) {a[i] = in.nextInt();int x = a[i];if (dic.containsKey(x)) {int cur = dic.get(x);int temp = 0;if (dic.containsKey(x-1)) {temp = dic.get(x-1);}cur = Math.max(cur, temp+1);dic.put(x, cur);}else {int temp = 0;if (dic.containsKey(x-1)) {temp = dic.get(x-1);}dic.put(x, temp+1);}int temp0 = dic.get(x);if (temp0>len) {len = temp0;idx = i;}}out.println(len);int now = a[idx];for (int i = idx;i >= 1;i--) {if (a[i]==now) {v.add(i);now--;}}for (int i = (int)v.size()-1;i >= 0;i--) {out.print(v.get(i)+" ");}}}static class InputReader{public BufferedReader br;public StringTokenizer tokenizer;public InputReader(InputStream ins) {br = new BufferedReader(new InputStreamReader(ins));tokenizer = null;}public String next(){while (tokenizer==null || !tokenizer.hasMoreTokens()) {try {tokenizer = new StringTokenizer(br.readLine());}catch(IOException e) {throw new RuntimeException(e);}}return tokenizer.nextToken();}public int nextInt() {return Integer.parseInt(next());}}
}
