Pagini recente » Cod sursa (job #43462) | Cod sursa (job #2605511) | Cod sursa (job #245308) | Cod sursa (job #2818179) | Cod sursa (job #87182)
Cod sursa(job #87182)
# include <stdio.h>
const long int MAXN=5000;
long int len,n,v[MAXN+1],solv[MAXN+1],sollen,solf;
struct {long int inf,next;} set[MAXN+1];
void citire()
{
FILE *f=fopen("subsir2.in","r");
fscanf(f,"%ld",&n);
long int i;
for (i=1;i<=n;i++) fscanf(f,"%ld",&v[i]);
fclose(f);
}
void calculeaza()
{
long int i,j,minsofar;
set[n].next=0;set[n].inf=1;
for (i=n-1;i>=1;i--)
{
set[i].inf=-1;set[i].next=0;
for (j=i+1,minsofar=-1;j<=n;j++)
{
//trebuie sa fie >=v[i] si <minsofar
if (v[j]>=v[i]&&(minsofar==-1||v[j]<minsofar))
{
minsofar=v[j];
//sa vedem daca e cumva o sol mai buna
if (set[i].inf==-1||set[i].inf>set[j].inf+1)
{
set[i].inf=set[j].inf+1;
set[i].next=j;
}
else if (set[i].inf==set[j].inf+1&&v[set[i].next]>v[j])
{
set[i].next=j;
}
}
}
if (minsofar==-1)
{
set[i].next=0;
set[i].inf=1;
}
}
//sa vedem care e castigatorul
sollen=-1;
for (i=1,minsofar=-1;i<=n;i++)
if (minsofar==-1||v[i]<minsofar)
{
minsofar=v[i];
if (sollen==-1||sollen>set[i].inf||(sollen==set[i].inf&&v[solf]>v[i]))
{
sollen=set[i].inf;
solf=i;
}
}
}
void scrie()
{
long int i,alr=0;
FILE *g=fopen("subsir2.out","w");
fprintf(g,"%ld\n",sollen);
for (;solf;solf=set[solf].next)
{
if (alr) fprintf(g," ");
fprintf(g,"%ld",solf);
alr++;
}
fprintf(g,"\n");
fcloseall();
}
int main()
{
citire();
calculeaza();
scrie();
return 0;
}