Pagini recente » Cod sursa (job #2535704) | Cod sursa (job #2409328) | Cod sursa (job #1154986) | Cod sursa (job #2786635) | Cod sursa (job #49113)
Cod sursa(job #49113)
#include<stdio.h>
#define NMAX 5000
int main(void)
{
int V[NMAX];
long int A[NMAX];
int T[NMAX];
int n;
int i,j;
int pmin;
int amin;
long max,min;
FILE *f;
//citeste datele de intarare
f=fopen("subsir2.in","rt");
fscanf(f,"%d",&n);
for(i=0;i<n;i++)
fscanf(f,"%ld",&A[i]);
fclose(f);
//face programare dinamica
V[n-1]=1;
T[n-1]=-1;
for(i=n-2;i>=0;i--)
{
//cauta cel mai lung subsir la care poate adauga elementul A[i]
max=0;
min=A[i+1];
amin=1000001;
for(j=i+1;j<n;j++)
{
if(A[j]>A[i])
if(((A[i]<min)&&(A[j]<min))||(i+1==j))
if(V[j]+1>max)
{
max=V[j]+1;
pmin=j;
amin=A[j];
} else
if(V[j]+1==max)
if(A[j]<amin)
{
pmin=j;
amin=A[j];
}
if(A[j]<min)
min=A[j]; //memoreaza valoarea minima de pana acuma
}
if(max!=0)
{
V[i]=max;
T[i]=pmin;
} else
{
V[i]=1;
T[i]=-1;
}
}
//afiseaza solutia
f=fopen("subsir2.out","wt");
fprintf(f,"%d\n",V[0]);
i=0;
while(i!=-1)
{
fprintf(f,"%d ",i+1);
i=T[i];
}
fprintf(f,"\n");
fclose(f);
//sf
return 0;
};