Cod sursa(job #1330804)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 30 ianuarie 2015 23:13:32
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <cstdio>

#define INF 0x3f3f3f3f
#define Nmax 5005


using namespace std;

int N,v[Nmax],DP[Nmax],daddy[Nmax];
int apartine[Nmax];
int ans = INF,pz;

int mini(int a,int b)
{
    return a < b? a : b;
}

void Read()
{
    scanf("%d",&N);
    for(int i = 1; i <= N; ++i)
        scanf("%d",v+i);
}

void Solve()
{
    int minim;
    for(int i = N ; i >= 1; --i)
    {
        DP[i] = INF;
        minim = INF;
        for(int j = i + 1; j <= N; ++j)
        {
            if(v[j] >= v[i])
                apartine[j] = 1;
            if(v[j] >= v[i] && v[j] < minim) /// aleg minimul mai mare ca v[i] ca
            {                                /// sigur e cel mai bun
                minim = v[j];
                if(DP[j] + 1 <= DP[i])
                {
                    if(DP[j] + 1 < DP[i])
                    {
                        DP[i] = DP[j] + 1;
                        daddy[i] = j;
                        continue;
                    }
                    if(v[daddy[i]] > v[j])
                        daddy[i] = j;
                }
            }
        }
        if(DP[i] == INF)
        {
            DP[i] = 1;
            daddy[i] = N + 1;
        }
    }
    for(int i = 1; i <= N; ++i)
        if(!apartine[i])
        {
            if(ans > DP[i]){
                ans = DP[i];
                pz = i;
            }
            else
                if(ans == DP[i] && v[i] < v[pz])
                        pz = i;
        }
}

void Print()
{
    printf("%d\n",ans);
    while(pz <= N)
    {
        printf("%d ",pz);
        pz = daddy[pz];
    }
}

int main()
{
    freopen("subsir2.in","r",stdin);
    freopen("subsir2.out","w",stdout);

    Read();
    Solve();
    Print();

    return 0;
}