Cod sursa(job #3040765)

Utilizator _andrei4567Stan Andrei _andrei4567 Data 30 martie 2023 13:48:30
Problema Secv Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 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];

struct da
{
    int last, len;
} dp[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)
    {
        dp[a[i]].len = INF;
        dp[a[i]].last = 0;
        if (a[i] == 1)
            dp[1].len = 0;
    }
    for (int i = 1; i <= n; ++i)
    {
        if (a[i] != 1)
            if (dp[a[i] - 1].last)
            dp[a[i]].len = min (dp[a[i]].len, dp[a[i] - 1].len + i - dp[a[i] - 1].last);
        //cout << dp[a[i]].last << ' ' << dp[a[i]].len << ' ';
        dp[a[i]].last = i;
    }
    cout << dp[norm.size()].len + 1 << '\n';
    return 0;
}