Pagini recente » Cod sursa (job #1379122) | Cod sursa (job #1061607) | Cod sursa (job #2121455) | Cod sursa (job #1345777) | Cod sursa (job #1957023)
#include <stdio.h>
using namespace std;
#define INF 2*10e9+1
#define MAX 5005
int v[MAX],l[MAX],nxt[MAX],t[MAX];
FILE*f=fopen("subsir2.in","r");
FILE*g=fopen("subsir2.out","w");
int main()
{
int n,i,p,j,mn;
fscanf(f,"%d",&n);
v[0]=INF;
for (i=1;i<=n;i++){
fscanf(f,"%d",&v[i]);
}
l[0]=INF;
for (i=n;i>=1;i--){
mn=INF;
p=0;
for (j=i+1;j<=n;j++){
if (v[j]<mn&&v[j]>=v[i]&&(l[j]<l[p]||(l[j]==l[p]&&v[j]<v[p]))) {p=j;}
if (v[j]>=v[i]) t[j]=1;
if (v[j]<mn&&v[j]>=v[i]) mn=v[j];
}
if (p){
l[i]=l[p]+1;
nxt[i]=p;
}
else {
nxt[i]=n+1;
l[i]=1;
}
}
mn=0;
for (i=1;i<=n;i++){
if (!t[i]&&(l[i]<l[mn]||(l[i]==l[mn]&&v[i]<v[mn]))) mn=i;
l[nxt[i]]=INF;
}
fprintf(g,"%d\n",l[mn]);
while (mn<=n){
fprintf(g,"%d ",mn);
mn=nxt[mn];
}
fclose(f);
fclose(g);
return 0;
}