Pagini recente » Cod sursa (job #1306464) | Cod sursa (job #63657) | Cod sursa (job #2237010) | Cod sursa (job #463630) | Cod sursa (job #1040809)
#include <stdio.h>
using namespace std;
FILE *f,*g;
int i,n,j,max1,v[5003],t[5003],a[5003],l[5003],poz,nr,urm[5003],p1,p2;
int main()
{f=fopen ("subsir2.in","r");
g=fopen ("subsir2.out","w");
fscanf (f,"%d",&n);
for (i=1;i<=n;i++) fscanf (f,"%d",&a[n-i+1]);
for (i=1;i<=n;i++)
{
for (j=i-1;j>=1;j--)
{
if (a[j]>=a[i] && ((l[j]+1<l[i] || l[i]==0) || (l[j]+1==l[i] && a[j]<a[v[i]])) && (t[j]==1 || (v[i]==0||(a[v[i]] >a[j] && (a[urm[j]]<a[i])))))
{
l[i]=l[j]+1;
v[i]=j;
t[j]=0;
urm[j]=i;
t[i]=1;
}
if (l[j]+1==l[i] && a[i]>a[urm[j]])
urm[i]=urm[j];
}
if (l[i]==0)
{
l[i]=1;
v[i]=i;
t[i]=1;}
}
max1=1000000000;
for (i=n;i>=1;i--)
{
if (t[i]==1 && l[i]<max1)
{
max1=l[i];
poz=i;
}
else if (l[i]==max1 && a[i]<a[poz] && t[i]==1)
{
max1=l[i];
poz=i;
}
else if (l[i]==max1 && a[i]==a[poz])
{
p1=i;p2=poz;
while (a[p1]==a[p2])
{
p1=v[p1];
p2=v[p2];
}
if (a[p1]<a[p2])
{
max1=l[i];
poz=i;
}
}
}
while (v[poz]!=poz)
{
t[++nr]=poz;
poz=v[poz];
}
t[++nr]=poz;
fprintf (g,"%d\n",max1);
for (i=1;i<=nr;i++)
fprintf (g,"%d ",n-t[i]+1);
return 0;
}