Pagini recente » Cod sursa (job #187633) | Cod sursa (job #187640) | Cod sursa (job #3133345) | Cod sursa (job #202197) | Cod sursa (job #3332087)
#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 = -1;
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 = -1;
int cmb = 0,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 + 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;
if(ok)
rez = aux;
}
}
fout<<rez.size()<<"\n";
for(auto i : rez)
fout<<i<<" ";
return 0;
}