Pagini recente » Diferente pentru problema/progresii intre reviziile 8 si 7 | Monitorul de evaluare | Diferente pentru problema/progresii intre reviziile 4 si 3 | Cod sursa (job #1991759) | Cod sursa (job #3332088)
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
int main()
{
int n;
fin>>n;
vector<int>a(n+1),pr(n+1,-1),dp(n+1,0),mx_sfx(n+1,1);
vector<int>rez;
for(int i=1;i<=n;i++){
fin>>a[i];
}
int mx = -1e9;
for(int i=n;i>=1;i--){
if(a[i] <= mx)
mx_sfx[i] = 0;
mx = max(mx,a[i]);
}
for(int i=1;i<=n;i++){
int mmx = -1e9;
int cmb = 1e9,id=-1;
for(int j=i-1;j>=1;j--){
if(mmx < a[j] && cmb > dp[j] && a[j] <= a[i]){
cmb = dp[j];
id = j;
}
if(a[j] <= a[i])
mmx = max(mmx,a[j]);
}
dp[i] = (cmb == 1e9 ? 0 : cmb) + 1;
pr[i] = id;
if((rez.size() > dp[i] || rez.size() == 0) && mx_sfx[i]){
rez.clear();
int j = i;
while(j != -1){
rez.push_back(j);
j = pr[j];
}
reverse(rez.begin(),rez.end());
}
else if(rez.size() == dp[i] && mx_sfx[i]){
///care e mai mic lexicografic
bool ok = false;
vector<int>aux;
int j = i;
while(j != -1){
aux.push_back(j);
j = pr[j];
}
reverse(aux.begin(),aux.end());
for(int k=0;k<aux.size();k++)
if(a[aux[k]] < a[rez[k]])
ok = true;
else if(a[aux[k]] > a[rez[k]])
break;
if(ok)
rez = aux;
}
}
fout<<rez.size()<<"\n";
for(auto i : rez)
fout<<i<<" ";
return 0;
}