ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1651. Кратчайшая подцепь

why wrong 7
Послано mingotlik 26 авг 2012 13:55
I use dp code.
///////////////////


import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;


public class Timus_1651 {
    static StreamTokenizer st;
    public static void main(String[] args) throws IOException{
        st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = nextInt();
        int []a = new int [n+1];
        for (int i = 1; i <=n; i++) {
            a[i] = nextInt();
        }
        int []dp = new int [100001];
        int []p = new int [100001];
        int INF  = (int)1e8;
        Arrays.fill(dp, INF);
        dp[a[1]] = 0;
        for (int i = 2; i <=n; i++) {
            if (dp[a[i]] > dp[a[i-1]]+1){
                dp[a[i]] = dp[a[i-1]]+1;
                p[a[i]] = a[i-1];
            }
        }
        int cur = a[n];
        ArrayList<Integer> ans = new ArrayList<Integer>();
        while (true){
            ans.add(cur);
            if (cur == a[1]) break;
            cur = p[cur];
        }
        Collections.reverse(ans);
        for (int i = 0; i < ans.size(); i++) {
            out.write(ans.get(i)+" ");
        }
        out.close();
    }
    private static int nextInt() throws IOException{
        st.nextToken();
        return (int) st.nval;
    }

}