Pagini recente » Cod sursa (job #2785529) | Cod sursa (job #1260068) | Cod sursa (job #1092308) | Cod sursa (job #1213367) | Cod sursa (job #609625)
Cod sursa(job #609625)
#include<stdio.h>
#define MaxN 5010
const int INF = 21903912;
int A[MaxN];
int BST[MaxN];
int TST[MaxN];
int BDR[MaxN];
int TDR[MaxN];
int N;
int MIN = INF;
void citire(void)
{
FILE *f = fopen("subsir2.in","r");
fscanf(f,"%d",&N);
for(int i=1;i<=N;i++)
fscanf(f,"%d",&A[i]);
fclose(f);
}
void solveStanga(void)
{
int MAX;
for(int i=1;i<=N;i++)
{
MAX = -INF;
BST[i] = INF;
for(int j=i-1;j;j--)
if(A[j] <= A[i] && A[j] > MAX && BST[j] < BST[i])
{
MAX = A[j];
BST[i] = BST[j] + 1;
TST[i] = j;
}
else if(A[j] > MAX && A[j] <= A[i])
MAX = A[j];
if(BST[i] == INF)
BST[i] = 1;
}
}
void solveDreapta(void)
{
int MIN;
for(int i=N;i;i--)
{
MIN = INF;
BDR[i] = INF;
for(int j=i+1;j<=N;j++)
if(A[j] >= A[i] && A[j] < MIN && BDR[j] < BDR[i])
{
MIN = A[j];
BDR[i] = BDR[j] + 1;
TDR[i] = j;
}
else if(A[j] < MIN && A[j] >= A[i])
MIN = A[j];
if(BDR[i] == INF)
BDR[i] = 1;
}
}
void Afis(FILE *g,int P)
{
fprintf(g,"%d ",P);
if(TDR[P])
Afis(g,TDR[P]);
}
void FindMin(FILE *g)
{
int P;
for(int i=1;i<=N;i++)
if(BST[i] + BDR[i] - 1 < MIN)
{
MIN = BST[i] + BDR[i] - 1;
P = i;
}
fprintf(g,"%d\n",MIN);
Afis(g,P);
}
int main()
{
FILE *g = fopen("subsir2.out","w");
citire();
solveStanga();
solveDreapta();
FindMin(g);
// for(int i=1;i<=N;i++)
// printf("%d ",BST[i]);
// printf("\n");
// for(int i=1;i<=N;i++)
// printf("%d ",BDR[i]);
fclose(g);
return 0;
}