Cod sursa(job #3040786)

Utilizator _andrei4567Stan Andrei _andrei4567 Data 30 martie 2023 14:01:13
Problema Secv Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream cin ("secv.in");
ofstream cout ("secv.out");

const int INF = 1e9;

const int N = 5000;
int a[N + 1], dp[N + 1], ant[N + 1];

vector <int> norm;

int n;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i], norm.push_back(a[i]);
    sort (norm.begin(), norm.end());
    vector <int> :: iterator it = unique (norm.begin(), norm.end());
    norm.resize(distance (norm.begin(), it));
    for (int i = 1; i <= n; ++i)
        a[i] = lower_bound (norm.begin(), norm.end(), a[i]) - norm.begin() + 1;
    for (int i = 1; i <= n; ++i)
    {
        ant[a[i]] = INF;
        if (a[i] == 1)
            dp[i] = 0;
        else
            dp[i] = INF;
    }
    for (int i = 1; i <= n; ++i)
    {
        if (a[i] != 1)
            if (ant[a[i] - 1] != INF && dp[ant[a[i] - 1]] != INF)
                dp[i] = min (dp[i], dp[ant[a[i] - 1]] + i - ant[a[i] - 1]);
        ant[a[i]] = i;
    }
    int mn = INF;
    for (int i = 1; i <= n; ++i)
        if (a[i] == norm.size())
            mn = min (mn, dp[i]);
    if (mn == INF)
        mn = -2;
    cout << mn + 1 << '\n';
    return 0;
}