Witam.
Rozwiązuję to zadanie << https://szkopul.edu.pl/problemset/problem/KkZDP16mELVF692Bf-NJsN1L/site/?key=statement. Nie mam pojęcia dlaczego nie przechodzi mi mój kod większości przypadków w testach. Ogólnie to wyznaczam końce i początki dla vectora bracia -> preprocessinguję tablicę początków i końców -> wyznaczam początek i koniec dla preprocessingu -> robię dp
Będę wdzięczny jak ktoś może rzucić oko na kod.
Z góry dziękuję.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 1e6 + 5;
int poczatek[maxn];
int koniec[maxn];
std::vector<int> bracia;
std::vector<int> preprocessing;
int dp[maxn*2];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
bracia.push_back(0);
for(int i=1;i<=n;++i){
int x;
std::cin >> x;
bracia.push_back(x);
}
//poczatek dla bracia
for(int i=1;i<=n;++i)
poczatek[i] = -1;
for(int i=1;i<=n;++i)
if(poczatek[bracia[i]] == -1)
poczatek[bracia[i]] = i;
//koniec dla bracia
for(int i=1;i<=n;++i)
koniec[i] = -1;
for(int i=n;i>=1;--i)
if(koniec[bracia[i]] == -1)
koniec[bracia[i]] = i;
//preprocessing 3 2 4 2 5 - > 3 3 2 4 4 2 5 5
preprocessing.push_back(0);
for(int i=1;i<=n;++i){
if(poczatek[bracia[i]] == koniec[bracia[i]])
{
preprocessing.push_back(bracia[i]);
preprocessing.push_back(bracia[i]);
}
else if(poczatek[bracia[i]] == i || koniec[bracia[i]] == i)
preprocessing.push_back(bracia[i]);
}
//poczatek dla preprocessing
for(int i=1;i<=preprocessing.size()-1;++i)
poczatek[i] = -1;
for(int i=1;i<=preprocessing.size()-1;++i)
if(poczatek[preprocessing[i]] == -1)
poczatek[preprocessing[i]] = i;
//koniec dla preprocessing
for(int i=1;i<=preprocessing.size()-1;++i)
koniec[i] = -1;
for(int i=preprocessing.size()-1;i>=1;--i)
if(koniec[preprocessing[i]] == -1)
koniec[preprocessing[i]] = i;
//dp
dp[0] = 0;
for(int i=1;i<=preprocessing.size()-1;++i){
if(i == koniec[preprocessing[i]])
dp[i] = max(dp[poczatek[preprocessing[i]]] + 1,dp[i-1]);
else
dp[i] = dp[i-1];
}
cout << dp[preprocessing.size()-1] << '\n';
return 0;
}