Pagini recente » Cod sursa (job #2154345) | Cod sursa (job #173677) | Cod sursa (job #202158) | Cod sursa (job #2754869) | Cod sursa (job #2014342)
#include <fstream>
#define nmax 5005
using namespace std;
fstream f1("subsir2.in", ios::in);
fstream f2("subsir2.out", ios::out);
int n, a[nmax], t[nmax], nu[nmax];
long int v[nmax];
///a[i]= lungimea celui mai scurt subsir cresc maximal care incepe de pe poz i
///t[i]= indicele urmatorului el in cel mai scurt subsor maximal care incepe de pe poz i
void citire()
{
int i, j;
long int mini, ind;
f1>>n;
for(i=1; i<=n; i++) f1>>v[i];
a[n]=1;
t[n]=0;
for(i=n-1; i>=1; i--)
{
mini=0; ///=min (v[k], j>k>i) a.i v[k]>=v[i]
ind=0;
for(j=i+1; j<=n; j++)
if((v[i]<=v[j])&&((!mini)||(v[j]<mini)))
{
mini=v[j];
if((!ind)||((a[ind]> a[j])||((a[ind]==a[j])&&(v[ind]> v[j])))) ind=j;
}
a[i]=a[ind]+1;
t[i]=ind;
}
}
void afisare()
{
int i, ind=0;
long int mini;
mini=v[1];
for(i=2; i<=n; i++)
if(mini> v[i]) mini=v[i];
else nu[i]=1; ///subsirul poate fi extins la stanga
///cauti a[i] minim nu[i]=0 si v[i] minim
i=1;
while((i<=n)&&(nu[i])) i++;
if(i<=n) {mini=a[i];ind=i;}
while(i<=n)
{
if((!nu[i])&&((a[i]< mini)||((a[i]==mini)&&(v[i]< v[ind])))) {mini=a[i];ind=i;}
i++;
}
f2<<mini<<"\n";
while(ind)
{
f2<<ind<<' ';
ind=t[ind];
}
}
int main()
{
citire();
afisare();
return 0;
}