Cod sursa(job #2022605)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 16 septembrie 2017 19:56:39
Problema Subsir 2 Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <fstream>
#include <vector>
#include <queue>
#define VAL 5005
#define INF 0x3f3f3f

using namespace std;

ifstream fin("subsir2.in");
ofstream fout("subsir2.out");

int N, i, j, mn, mx, v[VAL];
int dp[VAL], prec[VAL], poz;
bool okb[VAL], oke[VAL];
vector <int> G[VAL], SOL;
queue <int> Q;

void BFS(int nod)
{
    int i;
    dp[nod]=1;
    Q.push(nod);
    while (Q.empty()==false)
    {
        nod=Q.front();
        Q.pop();
        for (i=G[nod].size()-1; i>=0; i--)
        {
            if (dp[G[nod][i]]==dp[nod]+1 && v[nod]<v[prec[G[nod][i]]])
            {
                Q.push(G[nod][i]);
                prec[G[nod][i]]=nod;
            }
            if (dp[G[nod][i]]>dp[nod]+1)
            {
                dp[G[nod][i]]=dp[nod]+1;
                Q.push(G[nod][i]);
                prec[G[nod][i]]=nod;
            }
        }
    }
}

int main()
{
    fin >> N;
    mn=INF;
    for (i=1; i<=N; i++)
    {
        fin >> v[i];
        dp[i]=INF;
        if (v[i]<mn)
        {
            mn=v[i];
            okb[i]=true;
        }
    }
    mx=-INF;
    for (i=N; i>=1; i--)
    {
        mn=INF;
        for (j=i+1; j<=N; j++)
        {
            if (v[j]>=v[i] && mn>v[j])
            {
                mn=v[j];
                G[i].push_back(j);
            }
        }
        if (v[i]>mx)
        {
            mx=v[i];
            oke[i]=true;
        }
    }
    for (i=N; i>=1; i--)
      if (okb[i]==true)
        BFS(i);
    mn=INF;
    for (i=N; i>=1; i--)
    {
        if (oke[i]==true && mn>dp[i])
        {
            mn=dp[i];
            poz=i;
        }
    }
    fout << mn << '\n';
    while (poz>0)
    {
        SOL.push_back(poz);
        poz=prec[poz];
    }
    for (i=mn-1; i>=0; i--)
      fout << SOL[i] << " ";
    fin.close();
    fout.close();
    return 0;
}