Pagini recente » Cod sursa (job #78197) | Cod sursa (job #1791601) | Cod sursa (job #2903495) | Cod sursa (job #878101) | Cod sursa (job #1397431)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
const int Nmax = 5005;
const int oo = 0x3f3f3f3f;
int N, V[Nmax], Tat[Nmax], Lg[Nmax];
int main()
{
fin>>N;
for(int i=1; i<=N; i++)
fin>>V[i];
for(int i=N; i; i--)
{
Lg[i] = oo; int poz = 0;
for(int j=i+1; j <= N ;j++)
if(V[i] <= V[j])
{
if(!poz || V[j] < V[poz]) poz = j;
if(poz && (Lg[poz] + 1 < Lg[i] || (Lg[poz] + 1 == Lg[i] && V[poz] < V[Tat[i]])))
{
Lg[i] = Lg[poz] + 1;
Tat[i] = poz;
}
}
if(Lg[i] == oo) Lg[i] = 1;
}
int sol = oo, solpoz = 0, poz = 0;
for(int i=1; i<=N; i++)
{
if(!poz || V[poz] > V[i])
{
poz = i;
if(sol > Lg[i] || (sol == Lg[i] && V[i] < V[solpoz]))
{
sol = Lg[i];
solpoz = i;
}
}
}
fout<<sol<<'\n';
while(solpoz)
{
fout<<solpoz<<' ';
solpoz = Tat[solpoz];
}
return 0;
}