è da ieri che sto cercando di capire questo problema ma c è un aspetto che non riesco a comprendere
either Sj < Sj+1 or Sj+1 = CSj
vuol dire che se io ho una nota che soddisfi entrambe le condizioni non la devo accettare ?
tipo
4
1 2 2 2
2 3 4 5
qui stamperebbe 1 o 2 ?
io ho provato con un approccio dp(ancora non ottimizzato),ma mi sbaglia i primi due sub del 2°subtask.
Non credo che intendessero exclusive or, almeno la mia sol non lo prende in considerazione , sarà un normalissimo bug nel codice.
perchè ho provato con una semplice quadratica che poi andrò a sostituire con una N*log N ma non riesco a capire dove sbaglia
e penso sia un problema di mancata comprensione della traccia qui linko il code ->
ho modificato il code rendendolo una vera e propria dp quadratica ma non funziona xd:
#include <bits/stdc++.h>
using namespace std;
int dp[100001];
int main()
{
int N;
cin>>N;
int vet[N],ret[N];
for(int i=0;i<N;i++){
cin>>vet[i];
}
for(int i=0;i<N;i++){
cin>>ret[i];
}
int sol=-1;
for(int i=0;i<N;i++){
for(int j=i+1;j<N;j++){
if(vet[i]<vet[j] || ret[i]==vet[j]){
dp[j]=max(dp[j],dp[i]+1);
}
}
sol=max(sol,dp[i]);
}
cout<<sol+1;
}
ok ho risolto avevo compreso male la traccia xd
Ah bene, infatti non capivo molto del codice