Cod sursa(job #1251052)

Utilizator sebinechitasebi nechita sebinechita Data 28 octombrie 2014 21:36:59
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
#define MAX 5002
#define cout fout
#define INF (1<<30)
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];
    }
    a[n+1]=INF;
    b[n+1]=0;
    n++;
    a[0]=-INF;
    for(i=n-1;i>=0;i--)
    {
        p[i]=n;
        b[i]=n+2;
        int minim=INF+1;
        for(j=i+1;j<=n;j++)
        {
            if(a[j]>=a[i])
            {
                if(a[j]<minim)
                {
                    if(b[j]==b[i] && a[p[i]]>a[j])
                        p[i]=j;
                    if(b[j]<b[i])
                        p[i]=j;
                    b[i]=min(b[i], b[j]);
                }
                minim=min(minim, a[j]);
            }
        }
        b[i]++;
    }
    i=p[0];
    cout << b[0]-1 << "\n";
    while(i!=n)
    {
        cout << i << ' ';
        i=p[i];
    }
    cout << "\n";

}