Pagini recente » Cod sursa (job #299631) | Cod sursa (job #1599824) | Cod sursa (job #1391644) | Cod sursa (job #1800547) | Cod sursa (job #944238)
Cod sursa(job #944238)
#include <fstream>
#define In "subsir2.in"
#define Out "subsir2.out"
#define Nmax 5002
#define val_max 1000100
using namespace std;
int Lis[Nmax+2],next[Nmax+2],a[Nmax+2];
int n,start,L;
///Lis[i] = lungimea minima a subsirului crescator maximal care incepe cu a[i]
bool viz[Nmax+2];
ofstream g(Out);
inline void Citire()
{
ifstream f(In);
f>>n;
for(int i=1;i<=n;i++)
f>>a[i];
f.close();
}
inline void Dinamic()
{
int i,j,minm;
Lis[n] = 1;
for(i = n-1; i ;i--)
{
Lis[i] = Nmax;
minm = val_max;
for(j=i+1;j<=n;j++)
{
if(a[i]<=a[j]&& a[j]<minm)
{
viz[j] = true;
minm = a[j];
if(Lis[i]>Lis[j]+1)
{
Lis[i] = Lis[j]+1;
next[i] = j;
}
else
if(Lis[i]==Lis[j]+1&&a[next[i]]>a[j])
next[i] = j;
}
}
if(Lis[i]==Nmax)
Lis[i] = 1;
}
}
inline void Afisare()
{
int i;
L = Nmax;
for(i=1;i<=n;i++)
if(viz[i]==false)
{
if(Lis[i]<L)
{
L = Lis[i];
start = i;
}
else
if(Lis[i] ==L &&a[start]>a[i])
start = i;
}
g<<L<<"\n";
while(start)
{
g<<start<<" ";
start = next[start];
}
g<<"\n";
g.close();
}
int main()
{
Citire();
Dinamic();
Afisare();
return 0;
}