Pagini recente » Cod sursa (job #1260008) | Cod sursa (job #2153779) | Cod sursa (job #2906412) | Cod sursa (job #528599) | Cod sursa (job #2020284)
#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], son[MaxN], maxs[MaxN], Min, minlen, start, st[MaxN];
void print(int k)
{
if (k == 0)
return;
print(son[k]);
fprintf(f2, "%d ", k);
}
int main()
{
fscanf(f1, "%d\n", &n);
for (i = 1; i <= n; i++)
{
fscanf(f1, "%d", &v[i]);
st[i] = 1000001;
}
fclose(f1);
maxs[n] = v[n];
for (i = n - 1; i >= 1; i--)
if (v[i] > maxs[i+1])
maxs[i] = v[i];
else
maxs[i] = maxs[i+1];
length[1] = 1; son[1] = 0;
pos[n] = 1;
if (v[1] > maxs[2])
pos[1] = 1;
for (i = 2; i <= n; i++)
{
minlen = MaxN;
Min = 1000001;
for (j = 1; j <= i - 1; j++)
if (v[j] <= v[i] && minlen > 1 + length[j] && v[i] < st[j])
{
minlen = 1 + length[j];
Min = v[j];
son[i] = j;
}
else if (v[j] <= v[i] && minlen == 1 + length[j] && Min > v[j] && v[i] < st[j])
{
Min = v[j];
son[i] = j;
}
if (minlen == MaxN)
{
length[i] = 1;
son[i] = 0;
}
else
{
length[i] = minlen;
}
if (v[i] > maxs[i+1])
pos[i] = 1;
for (j = 1; j <= i-1; j++)
if (st[j] > v[i])
st[j] = v[i];
}
minlen = MaxN;
Min = 1000001;
for (i = 1; i <= n; i++)
{
if (pos[i] == 1)
{
if (minlen > length[i])
{
minlen = length[i];
start = i;
Min = v[i];
}
else if (minlen == length[i] && Min > v[i])
{
Min = v[i];
start = i;
}
}
}
fprintf(f2, "%d\n", minlen);
print(start);
fclose(f2);
return 0;
}