Cod sursa(job #1761711)

Utilizator andrei1299Ghiorghe Andrei Alexandru andrei1299 Data 22 septembrie 2016 19:16:42
Problema Subsir 2 Scor 59
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int a[5005],n,din[5050],trace[5050];

void Citire()
{
    ifstream fin("subsir2.in");
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>a[i];
    fin.close();
}

void Solutie()
{
    a[n+1]=inf-1;
    for(int i=n;i>=0;i--)
    {
        int mini2=inf,mini=inf,pos;
        for(int j=i+1;j<=n+1;j++)
        {
            if(a[i]<a[j] && a[j]<mini)
            {
                if(din[j]<=mini2)
                {
                    mini2=din[j];
                    pos=j;
                }
                mini=a[j];
            }
        }
        din[i]=din[pos]+1;
        trace[i]=pos;
    }
}

ofstream fout("subsir2.out");

void Afisare()
{
    fout<<din[0]-1<<"\n";
    for(int i=trace[0];i<=n;i=trace[i])
        fout<<i<<" ";
}

int main()
{
    Citire();
    a[0]=-inf;
    Solutie();
    Afisare();
        fout.close();
    return 0;
}