Cod sursa(job #1135273)

Utilizator andreiagAndrei Galusca andreiag Data 7 martie 2014 16:43:34
Problema Subsir 2 Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <iostream>
#include <string>
#include <fstream>

using namespace std;
const int Nmax = 5005;
const int INF = 10000000;

int A[Nmax];
int D[Nmax];    // lungimea celui mai scurt subsir maximal
int P[Nmax];    // parinte
int Res[Nmax];

int main()
{
    ifstream f ("subsir2.in");
    ofstream g ("subsir2.out");
    
    int N;
    f >> N;
    
    for (int i = 0; i < N; i++)
    {
        f >> A[i];
        P[i] = -1;
        D[i] = 1;
    }
    
    int premax;
    for (int i = 1; i < N; i++)
    {
        premax = -INF;
        for (int j = i-1; j >-1; j--) {
            if (A[j] <= A[i] && A[j] > premax) {
                premax = A[j];
                if (D[i] == 1 || D[j]+1 < D[i])
                {
                    D[i] = D[j]+1;
                    P[i] = j;
                }
            }
        }
    }
    premax = -INF;
    int best = INF;
    int start = -1;

    for (int i = N-1; i >-1; i--) {
        if (A[i] > premax) {
            premax = A[i];
            if (best > D[i])
            {
                best = D[i];
                start = i;
            }
        }
    }
/*
    g << premax << '\t' << best << '\t' << start << endl;
    for (int i = 0; i < N; i++)
        g << D[i] << '_';
    g << endl;
    for (int i = 0; i < N; i++)
        g << P[i] << '_';
    g << "\nAnswer:\n";
*/
/*
    for (int i = N-1; i >-1; i--)
        if (D[i] == best) { start = i; break; }
*/
    int cnt = 0;
    while (start > -1) {
        Res[cnt] = start+1;
        start = P[start];
        cnt++;
    }
    g << best << '\n';
    for (int i = cnt-1; i>-1; i--)
        g << Res[i] << ' ';
    g << '\n';

    return 0;
}