Cod sursa(job #1920933)

Utilizator lulian23Tiganescu Iulian lulian23 Data 10 martie 2017 10:41:28
Problema Subsir 2 Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <bits/stdc++.h>
#define MIN 1000001

using namespace std;

int n, a[ 5001 ], v[ 5001 ], sol[ 5001 ],  minn , s, p, k;

int main(){
    ifstream cin("subsir2.in");
    ofstream cout("subsir2.out");
    cin >> n;
    for (int i = 1; i <= n; i++)
     cin >> a[ i ];
    for (int i = n; i > 0; i--){
         s = minn = MIN;
     for (int j = i + 1; j <= n; j++)
         if (a[ j ] < minn && a[ i ] <= a[ j ]){
           minn = a[ j ];
           if (sol[ j ] <= MIN)
               s = sol[ j ], p = j;
         }
          if (minn == MIN)
            sol[ i ] = 1;
          else{
            sol[ i ] = sol[ p ] + 1;
            v[ i ] = p;
          }
    }
      minn = sol[ 1 ], p = 1 ,k = a[ 1 ];
    for (int i = 2; i <= n; ++i)
        if (a[ i ] < k){
            k = a[ i ];
            if (sol[ i ] <=minn)
                minn = sol[ i ],p = i;
        }
    cout << minn << '\n' << p << " ";
     while (--minn){
         p = v[ p ];
         cout << p << " ";
     }
    return 0;
}