Cod sursa(job #2020284)

Utilizator Dan_RadulescuRadulescu Dan Dan_Radulescu Data 9 septembrie 2017 18:52:10
Problema Subsir 2 Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.1 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], 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;
}