Cod sursa(job #1250272)

Utilizator sebinechitasebi nechita sebinechita Data 27 octombrie 2014 22:44:42
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
#define MAX 5002

int a[MAX], b[MAX], p[MAX];

int main()
{
    int n, i, j, maxi;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>a[i];
    }
    for(i=n;i>=1;i--)
    {
        p[i]=n+1;
        for(j=i+1;j<=n;j++)
        {
            if(a[j]>a[i] && b[j]+1>=b[i])
            {
                b[i]=b[j]+1;
                p[i]=j;
            }
            if(a[j]>a[i] && b[j]+1==b[i] && a[p[i]]>a[j])
            {
                p[i]=j;
            }
        }
    }
    maxi=1;
    for(i=1;i<=n;i++)
    {
        if(b[maxi]<b[i])
            maxi=i;
        if(b[maxi]==b[i] && a[maxi]>a[i])
            maxi=i;
    }
    fout << b[maxi]+1 << endl;
    while(maxi!=n+1)
    {
        fout << maxi << " ";
        maxi=p[maxi];
    }
    fout << endl;

}