Cod sursa(job #3263019)

Utilizator vicvicGriga Victor-Cristian vicvic Data 12 decembrie 2024 19:18:16
Problema Subsir 2 Scor 96
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.74 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=1;i<=n;i++)
    {
        dp[i]=1e9+1;
        int mx=-1e9-1;
        for (int j=i-1;j>=1;j--)
        {
            if (v[j]<=v[i] && v[j]>mx && dp[j]+1<dp[i])
            {
                dp[i]=dp[j]+1;
                before[i]=j;
            }
            if (v[j]<=v[i])
            {
                mx=max (mx, v[j]);
            }
        }
        if (dp[i]==1e9+1)
        {
            dp[i]=1;
            before[i]=-1;
        }
    }
    int mx=-1e9-1, ans=1e9+1;
    for (int i=n;i>=1;i--)
    {
        if (v[i]>mx)
        {
            mx=v[i];
            ans=min (ans, dp[i]);
        }
    }
    g << ans << "\n";
    mx=-1e9-1;
    for (int i=n;i>=1;i--)
    {
        if (dp[i]==ans && v[i]>mx)
        {
            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);
            reverse (crt.begin(), crt.end());
            reverse (crt2.begin(), crt2.end());
            if (crt<vec || vec.size()==0)
            {
                vec=crt;
                vec2=crt2;
            }
        }
        mx=max (mx, v[i]);
    }
    for (auto nr : vec2)
    {
        g << nr << " ";
    }
    return 0;
}