Cod sursa(job #1330780)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 30 ianuarie 2015 22:49:36
Problema Subsir 2 Scor 59
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 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 = 999999,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()
{
    for(int i = N ; i >= 1; --i)
    {
        DP[i] = INF;
        for(int j = i + 1; j <= N; ++j)
            if(v[j] >= v[i])
            {
                apartine[j] = 1;

                int bad = 0;
                for(int k = i + 1; k < j; ++k)
                        if(v[i] <= v[k] && v[k] <= v[j])
                        {
                            bad = 1;
                            break;
                        }
                if(!bad)
                    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])
        {
            ans = mini(ans,DP[i]);
            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;
}