Cod sursa(job #2238516)

Utilizator xRoALexBirtoiu Alexandru xRoALex Data 6 septembrie 2018 04:37:58
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <cstdio>
#define Nmax 5005
#define INF 1000010
using namespace std;

FILE *f=fopen("subsir2.in","r");
FILE *g=fopen("subsir2.out","w");

int v[Nmax],dp[Nmax],next[Nmax];
int n;

void citire()
{
    fscanf(f,"%d",&n);
    for(int i=1;i<=n;i++)
        fscanf(f,"%d",&v[i]);
}

void rezolva()
{
    for(int i=n;i>=1;i--)
    {
        int val = INF;
        int ind = 0;
        for(int j=i+1;j<=n;j++)
            if(v[j]<val && v[i] <= v[j])
            {
                if(ind == 0 || dp[j] <= dp[ind])
                    ind = j;
                val = v[j];
            }
        next[i] = ind;
        dp[i] = dp[ind] +1;
    }

    int val = v[1];
    int ind = 1;

    for(int i=2; i<=n; i++)
        if(v[i]<val)
            {
                if(dp[i] <= dp[ind])
                    ind =i;
                val = v[i];
            }

    fprintf(g,"%d\n",dp[ind]);
    while(ind)
    {
        fprintf(g,"%d ",ind);
        ind = next[ind];
    }
}

int main()
{
    citire();
    rezolva();
    return 0;
}