Cod sursa(job #1097017)

Utilizator andreiiiiPopa Andrei andreiiii Data 2 februarie 2014 20:57:12
Problema Subsir 2 Scor 92
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <algorithm>
#include <cstdio>
#include <bitset>

using namespace std;

const int N=5005, INF=0x3f3f3f3f;

int a[N], b[N], nxt[N];
bool v[N];

int main()
{
    freopen("subsir2.in", "r", stdin);
    freopen("subsir2.out", "w", stdout);
    int n, i, j, mins=INF, sol=INF, soli;
    scanf("%d", &n);
    for(i=1;i<=n;i++) scanf("%d", &a[i]);
    for(i=1;i<=n;i++)
    {
        if(a[i]<mins)
        {
            v[i]=1;
            mins=a[i];
        }
    }
    for(i=n;i;i--)
    {
        mins=INF;
        b[i]=INF;
        for(j=i+1;j<=n+1;j++)
        {
            if(a[j]>=a[i]&&a[j]<mins)
            {
                if(b[j]<b[i])
                {
                    b[i]=b[j];
                    nxt[i]=j;
                }
                else if(b[j]==b[i]&&a[j]<a[nxt[i]]) nxt[i]=j;
                mins=a[j];
            }
        }
        if(b[i]==INF) b[i]=0;
        b[i]++;
    }
    for(i=1;i<=n;i++)
    {
        if(v[i])
        {
            if(b[i]<sol)
            {
                sol=b[i];
                soli=i;
            }
            else if(b[i]==sol&&a[i]<a[soli]) soli=i;
        }
    }
    printf("%d\n", sol);
    for(i=soli;i;i=nxt[i]) printf("%d ", i);
}