Cod sursa(job #2022804)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 17 septembrie 2017 12:44:39
Problema Subsir 2 Scor 96
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.27 kb
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#define VAL 5005
#define INF 1000000000

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, M;
bool okb[VAL], oke[VAL];
vector <int> G[VAL], SOL[VAL];
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)
            {
                dp[G[nod][i]]=dp[nod]+1;
                Q.push(G[nod][i]);
                prec[G[nod][i]]=nod;
            }
        }
    }
}

bool Check(int a, int b)
{
    for (int i=0; i<G[a].size(); i++)
      if (G[a][i]==b)
        return true;
    return false;
}

void NewSOL(int poz, int mn)
{
    int i;
    M++;
    SOL[M].push_back(poz);
    mn--;
    for (i=poz-1; i>0; i--)
    {
        if (dp[i]==mn && Check(i, poz)==true)
        {
            poz=i;
            SOL[M].push_back(i);
            mn--;
            if (mn==0)
              break;
        }
    }
}

bool cmp(vector <int> A, vector <int> B)
{
    int i;
    for (i=A.size()-1; i>=0; i--)
      if (v[A[i]]!=v[B[i]])
        return v[A[i]]<v[B[i]];
    return false;
}

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';
    for (i=N; i>=1; i--)
      if (oke[i]==true && mn==dp[i])
        NewSOL(i, mn);
    sort(SOL+1, SOL+M+1, cmp);
    for (i=mn-1; i>=0; i--)
      fout << SOL[1][i] << " ";
    fin.close();
    fout.close();
    return 0;
}