Cod sursa(job #1399812)

Utilizator Ionut228Ionut Calofir Ionut228 Data 24 martie 2015 22:18:39
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <fstream>

using namespace std;

ifstream fin("subsir2.in");
ofstream fout("subsir2.out");

const int INF = 0x3f3f3f3f;

int N;
int pos, sol;
int V[5005], dp[5005], TT[5005];
bool inSubsir[5005];

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])
                inSubsir[j] = true;
            if (V[j] >= V[i] && V[j] < minim)
            {
                minim = V[j];
                if (dp[j] + 1 <= dp[i])
                {
                    if (dp[j] + 1 < dp[i])
                        TT[i] = j;
                    else if (dp[j] + 1 == dp[i])
                    {
                        if (V[j] < V[TT[i]])
                            TT[i] = j;
                    }
                    dp[i] = dp[j] + 1;
                }
            }
        }
        if (dp[i] == INF)
        {
            dp[i] = 1;
            TT[i] = N + 1;
        }
    }

    sol = INF;
    for (int i = 1; i <= N; ++i)
        if (!inSubsir[i])
        {
            if (dp[i] <= sol)
            {
                if (dp[i] < sol)
                    pos = i;
                else if (dp[i] == sol)
                {
                    if (V[i] < V[pos])
                        pos = i;
                }
                sol = dp[i];
            }
        }
}

int main()
{
    fin >> N;
    for (int i = 1; i <= N; ++i)
        fin >> V[i];

    solve();

    fout << sol << '\n';
    while (pos <= N)
    {
        fout << pos << ' ';
        pos = TT[pos];
    }
    fout << '\n';

    fin.close();
    fout.close();
    return 0;
}