Pagini recente » Cod sursa (job #1137406) | Cod sursa (job #2768424) | Cod sursa (job #979327) | Cod sursa (job #2663351) | Cod sursa (job #944221)
Cod sursa(job #944221)
#include <fstream>
#define In "subsir2.in"
#define Out "subsir2.out"
#define Nmax 5002
using namespace std;
int Lis[Nmax+2],prev[Nmax+2],a[Nmax+2],n,start,L;
///Lis[i] = lungimea minima a subsirului crescator maximal terminat in a[i]bool viz[Nmax+2];
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 Afisare(int x)
{
if(x!=Nmax)
{
Afisare(prev[x]);
g<<x<<" ";
}
}
inline void Dinamic()
{
int i,j,poz,maxx;
for(i=1;i<=n;i++)
{
Lis[i] = poz = Nmax;
maxx = 0;//maxx = el. maxim din secventa [j,i)
for(j=i-1;j;j--)
{
if(a[j]<=a[i]&&maxx<a[j])
{
if(Lis[i]>Lis[j]+1)
{
Lis[i] = Lis[j]+1;
poz = j;
}
else
if(Lis[i]==Lis[j]+1&&a[j]<a[poz])
poz = j;
viz[j] = true;
}
if(a[j]<=a[i] && maxx<a[j])
maxx = a[j];
}
if(Lis[i]==Nmax)
Lis[i] = 1;
prev[i] = poz;
}
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[i]<a[start])
start = i;
}
g<<L<<"\n";
Afisare(start);
g<<"\n";
g.close();
}
int main()
{
Citire();
Dinamic();
return 0;
}