Cod sursa(job #1525068)

Utilizator moise_alexandruMoise Alexandru moise_alexandru Data 14 noiembrie 2015 18:31:28
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("subsir2.in");
ofstream out("subsir2.out");

const int inf = 0x3f3f3f3f;
const int maxn = 5005;
int dp[maxn];
int a[maxn];
int dad[maxn];

int main()
{
    int n;
    in >> n;
    for(int i = 1; i <= n; i++)
        in >> a[i];
    /// dp[i] = cel mai mic subsirul crescator maximal care incepe
        /// pe pozitia i
    /// a[i]  < a[k] <  a[j]
    /// dad[i] = din cine am venit
    a[0] = -inf;
    for(int i = n; i >= 1; i--)
    {
        dp[i] = inf;
        int mn = inf;
        dad[i] = 0;
        for(int j = i + 1; j <= n ; j ++)
        {
            if(a[i] > a[j])
                continue;
            if(mn > a[j]) {
                if(dp[i] > dp[j] + 1 || (dp[i] == dp[j] + 1 && a[ dad[i] ] > a[j])) {
                    dad[i] = j;
                    dp[i] = dp[j] + 1;
                }
            }
            mn = min(mn, a[j]);
        }
        if(dp[i] == inf)
            dp[i] = 1;
    }

   /*** min(dp[j]) |
    nu exista un k***
    astfel incat
    aa[j] - false*/
    //for(int i = 1 ; i <= n ; ++ i)
    //    cout << dp[i] << ' ';
    int minim = inf;
    int mindp = inf;
    int st = 0;
    //cout << '\n';
    for(int i = 1 ; i <= n ; ++ i) {
        if(a[i] < minim) {
            if(mindp > dp[i] || (mindp == dp[i] && a[st] > a[i])) {
                mindp = dp[i];
                st = i;
            }
        }
        minim = min(minim, a[i]);
    }
    out << mindp << '\n';
    out << st << ' ';
    while(dad[st]) {
        out << dad[st] << ' ';
        st = dad[st];
    }
    return 0;
}