Cod sursa(job #1500806)
Utilizator | Boni Daniel Stefan refugiat | Data | 12 octombrie 2015 18:32:34 |
---|---|---|---|
Problema | Subsir 2 | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.79 kb |
#include<iostream>
#include<fstream>
#include<bitset>
using namespace std;
const int NMAX=5005;
const int inf=10000000;
int v[NMAX],lg[NMAX],suc[NMAX];
bitset<NMAX> extins;
int main()
{
ifstream si;
si.open("subsir2.in");
ofstream so;
so.open("subsir2.out");
int n;
si>>n;
int i;
for(i=1;i<=n;++i)
si>>v[i];
int j,k;
for(i=n;i>0;--i)
{
k=inf;
lg[i]=inf;
for(j=i+1;j<=n;++j)
{
if(k>v[j]&&v[i]<=v[j])
{
extins[j]=1;
k=v[j];
if(lg[j]+1<lg[i])
{
lg[i]=lg[j]+1;
suc[i]=j;
}
else
{
if(lg[i]==lg[j]+1)
{
if(v[suc[i]]>v[j])
suc[i]=j;
}
}
}
}
if(lg[i]==inf)
lg[i]=1;
}/*
for(i=1;i<=n;++i)
cout<<v[i]<<' ';
cout<<'\n';
for(i=1;i<=n;++i)
cout<<lg[i]<<' ';
cout<<'\n';
for(i=1;i<=n;++i)
cout<<v[suc[i]]<<' ';
cout<<'\n';
for(i=1;i<=n;++i)
cout<<extins[i]<<' ';
cout<<'\n';*/
int minn=inf,poz;
for(i=1;i<=n;++i)
{
if(!extins[i])
{
if(minn>lg[i])
{
minn=lg[i];
poz=i;
}
else
if(minn==lg[i])
if(v[i]<v[poz])
{
poz=i;
}
}
}
so<<minn<<'\n';
while(poz)
{
so<<poz<<' ';
poz=suc[poz];
}
so<<'\n';
return 0;
}