Pagini recente » Cod sursa (job #2291731) | Cod sursa (job #1623734) | Cod sursa (job #1702634) | Cod sursa (job #880947) | Cod sursa (job #2020300)
#include<bits/stdc++.h>
#define MaxN 5001
using namespace std;
FILE *f1 = fopen("subsir2.in", "r");
FILE *f2 = fopen("subsir2.out", "w");
int n, i, j, v[MaxN], pos[MaxN], length[MaxN], father[MaxN], maxs[MaxN], Min, minlen, start, st[MaxN];
void print(int k)
{
if (k == 0)
return;
fprintf(f2, "%d ", k);
print(father[k]);
}
int main()
{
fscanf(f1, "%d\n", &n);
for (i = 1; i <= n; i++)
fscanf(f1, "%d", &v[i]);
fclose(f1);
length[n] = 1;
for (i = n-1; i >= 1; i--)
{
Min = 1000001;
minlen = MaxN;
for (j = i + 1; j <= n; j++)
if (v[j] >= v[i] && Min >= v[j])
{
if (minlen > length[j])
minlen = length[j];
father[i] = j;
Min = v[j];
}
if (minlen == MaxN)
{
length[i] = 1;
}
else
{
length[i] = 1 + minlen;
}
}
Min = v[1];
pos[1] = 1;
for (i = 2; i <= n; i++)
if (Min > v[i])
{
Min = v[i];
pos[i] = 1;
}
minlen = MaxN;
Min = 1000001;
for (i = 1; i <= n; i++)
if (pos[i] == 1 && minlen > length[i])
{
minlen = length[i];
start = i;
Min = v[i];
}
else if (pos[i] == 1 && minlen == length[i] && Min > v[i])
{
Min = v[i];
start = i;
}
fprintf(f2, "%d\n", minlen);
print(start);
fclose(f2);
return 0;
}