Cod sursa(job #2007767)

Utilizator catalin9898Bajenaru Catalin catalin9898 Data 3 august 2017 23:38:57
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <iostream>
#include <cstdio>
using namespace std;
int v[5001],a[5001],t[5001],val,p;
bool bo[5001];
int main()
{
    int n,i,j,mi;
    freopen("subsir2.in","r",stdin);
    freopen("subsir2.out","w",stdout);
    scanf("%d",&n);
    for(i=1; i<=n; i++)
    {
        a[i]=1000001;
        scanf("%d",v+i);
    }
    a[0]=a[n+1]=1111111;
    a[n]=1;v[0]=-11111111;
    t[n]=n;
    for(i=n; i>=0; i--)
    {
        mi= 1000001;
        for(j=i+1; j<=n; j++)
        {
            if(v[j]<v[i])continue;
            if(mi>v[j])
            {
                mi=v[j];
                if(a[i]>a[j])
                {
                    a[i]=a[j]+1;
                    t[i]=j;
                }
            }
        }
        if(a[i]==1000001){a[i]=1;t[i]=i;}

    }
printf("%d\n",a[0]-1);

while(p!=t[p])
{
    printf("%d ",t[p]);
     p=t[p];
}

   /*
   val=mi=10000001;
    for(i=1;i<=n;i++)
    {j=i;if(!bo[i]){
        while(t[j]!=j&&(bo[j]==0))
        {   a[t[j]]=a[j];
            bo[j]=1;
            j=t[j];


        }bo[j]=1;
        if(mi>a[i]||(mi==a[i]&&v[i]<val)){val=v[i];mi=a[i];p=i; }
    }
    }
    printf("%d\n",mi);
    printf("%d ",p);
    while(p!=t[p])
    {
        printf("%d ",t[p]);p=t[p];
    }

*/

    return 0;
}