Cod sursa(job #1823902)

Utilizator raulmuresanRaul Muresan raulmuresan Data 6 decembrie 2016 23:02:08
Problema Subsir 2 Scor 82
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

const int Mn = 1e5 + 6;
const int oo = 1 << 30;

int n, ans,mn,poz,sol,minim;
int ar[Mn], dp[Mn], last[Mn];

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

    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &ar[i]);

    //ar[0] = -oo;
    for (int i = n; i >= 0; i--)
    {
        mn = oo;
        dp[i] = oo;
        for (int j = i + 1; j <= n; j++)
            if (mn > ar[j] && ar[i] <= ar[j])
            {
                mn = ar[j];
                if (dp[i] > dp[j] + 1)
                   dp[i] = dp[j] + 1, last[i] = j;
              else
                if (dp[i] == dp[j] + 1 && ar[last[i]] > ar[j])
                   last[i] = j;
            }

        if (dp[i] == oo)
           dp[i] = 1, last[i] = i;
    }
    mn = oo;
    poz = -1;
    sol = oo;
    minim = oo;
    for(int  i = 1; i <= n; i++)
    {
        if (mn > ar[i] && (dp[i] < sol || (dp[i] == sol && ar[last[i]] < minim)))
        {
            sol = dp[i];
            mn = ar[i];
            poz = i;
            minim = ar[last[i]];
            //printf("%d\n",i);
        }
        //printf("%d ",dp[i]);
    }
    //printf("%d\n", dp[0] - 1);
    printf("%d\n",sol);
    int it = poz;
    printf("%d ",poz);
    while (it != last[it] || it == 0)
    {
        it = last[it];
        printf("%d ", it);
    }

    //printf("\n");
    return 0;
}