Pagini recente » Cod sursa (job #2314331) | Cod sursa (job #2852868) | Cod sursa (job #587097) | Cod sursa (job #1267845) | Cod sursa (job #579997)
Cod sursa(job #579997)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
#define DIM 100001
int L[DIM], ANT[DIM], SOL[DIM], SF[DIM];
int n, a[DIM];
int main()
{
int smin = 1000000, i, j,poz,k,ok;
fin >> n;
for ( i = 0; i < n; ++i )
fin >> a[i];
for ( i = 0; i < n; ++i ){ ANT[i]=-1; SF[i]=1;}
for ( i = 0; i < n; ++i )
{
L[i] = 1;
for ( j = 0; j < i; ++j )
{ if ( L[j] + 1 > L[i] && a[i] > a[j] )
{ L[i] = L[j] + 1;
ANT[i]=j;
}
if(a[i] > a[j]) SF[j]=0;
}
}
/*for ( i = 0; i < n; ++i ) fout<<L[i]<<" ";
fout<<endl;
for ( i = 0; i < n; ++i ) fout<<ANT[i]<<" ";
fout<<endl;
for ( i = 0; i < n; ++i ) fout<<SF[i]<<" ";
fout<<endl;*/
for ( i = 0; i < n; ++i )
if ( smin > L[i] && SF[i]==1 )
{ ok=1;
for(k=i+1;k<n;k++) if(ANT[k]==i) ok=0;
if(ok)
{ smin = L[i];
poz=i;
}
}
fout << smin<<endl;
i=poz;
k=0;
while(ANT[i]!=-1)
{
SOL[k]=i+1; k++;
i=ANT[i];
}
SOL[k]=i+1;
for(i=k;i>=0;i--) fout<<SOL[i]<<" ";
fin.close();
fout.close();
return 0;
}