Cod sursa(job #2020300)

Utilizator Dan_RadulescuRadulescu Dan Dan_Radulescu Data 9 septembrie 2017 20:03:53
Problema Subsir 2 Scor 59
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#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;
}