Cod sursa(job #3263022)

Utilizator vicvicGriga Victor-Cristian vicvic Data 12 decembrie 2024 19:34:17
Problema Subsir 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f ("subsir2.in");
ofstream g ("subsir2.out");
int n, v[5005], dp[5005], before[5005];
vector <int> vec, crt, crt2, vec2;
int main()
{
    f >> n;
    for (int i=1;i<=n;i++)
    {
        f >> v[i];
    }
    for (int i=n;i>=1;i--)
    {
        dp[i]=1e9+1;
        int mn=1e9+1;
        for (int j=i+1;j<=n;j++)
        {
            if (v[j]>=v[i] && v[j]<mn)
            {
                mn=min (mn, v[j]);
                if (dp[j]+1<=dp[i])
                {
                    dp[i]=dp[j]+1;
                    before[i]=j;
                }
            }
        }
        if (dp[i]==1e9+1)
        {
            dp[i]=1;
            before[i]=-1;
        }
    }
    int mn=1e9+1, ans=1e9+1;
    for (int i=1;i<=n;i++)
    {
        if (v[i]<mn)
        {
            mn=v[i];
            ans=min (ans, dp[i]);
        }
    }
    g << ans << "\n";
    mn=1e9+1;
    for (int i=1;i<=n;i++)
    {
        if (dp[i]==ans && v[i]<mn)
        {
            crt.clear();
            crt2.clear();
            int el=i;
            while (before[el]!=-1)
            {
                crt.push_back (v[el]);
                crt2.push_back (el);
                el=before[el];
            }
            crt.push_back (v[el]);
            crt2.push_back (el);
            if (crt<vec || vec.size()==0)
            {
                vec=crt;
                vec2=crt2;
            }
        }
        mn=min (mn, v[i]);
    }
    for (auto nr : vec2)
    {
        g << nr << " ";
    }
    return 0;
}