Cod sursa(job #2063228)

Utilizator alexandruilieAlex Ilie alexandruilie Data 11 noiembrie 2017 10:19:07
Problema Subsir 2 Scor 12
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <fstream>

using namespace std;
ifstream f("subsir2.in");
ofstream g("subsir2.out");
int l[5001],a[5001],n,lmax,i;
struct ceva{int val,ind;}v[5001];
int verif(int i)
{
    for(int j=1;j<i;j++)
        if(a[j]<a[i]) return 0;
    return 1;
}
int valid (int i,int j)
{
    for(int w=i+1;w<j;w++)
        if(a[w]>=a[i]&&a[w]<=a[j]) return 0;
    return 1;
}
void solve()
{
    int i,j,mn,poz,mina=1000001,pozm;
    l[n]=1;v[1].val=a[n];v[1].ind=n;
    for(i=n-1;i>=1;i--)
    {
         mn=n+1;
        for(j=i+1;j<=n;j++)
        {
            if(a[i]<a[j]&&mn>l[j]&&valid(i,j)) mn=l[j];
        }
        if(mn==n+1) mn=0;
        l[i]=1+mn;
    }
    mn=l[1];poz=1;
    for(i=2;i<=n;i++)
    if(l[i]<=mn&&verif(i))
        {mn=l[i];
    poz=i;}
    g<<mn<<'\n'<<poz<<' ';
    mn--;
    while(mn)
    {
        mina=1000001;
        for(j=poz+1;j<=n;j++)
            if(l[j]==mn&&a[j]<mina&&valid(poz,j)) mina=a[j],pozm=j;
        poz=pozm;mn--;
        g<<poz<<' ';
    }
}
int main()
{
    f>>n;
    for(i=1;i<=n;i++) f>>a[i];
    for(i=1;i<=n;i++) v[i].val=1000001;
    solve();
    return 0;
}