Cod sursa(job #1696555)

Utilizator borscalinCalin-Stefan Georgescu borscalin Data 29 aprilie 2016 13:44:31
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <cstdio>
#define NMAX 5000
#define INF 1000001
using namespace std;

int v[NMAX + 1],dm[NMAX + 1],next[NMAX + 1]; /// lista simplu inlantuita
/// dm = cel mai scurt subsir maximal ce se termina pe poz i

int main(){
    freopen("subsir2.in","r",stdin);
    freopen("subsir2.out","w",stdout);
    int n,i,poz,min,j;
    scanf("%d",&n);
    for (i=1;i<=n;i++)
        scanf("%d",&v[i]);
    for (i=n;i>=1;i--){
        poz = next[i] = -1;
        dm[i] =  INF;
        for (j=i+1;j<=n;j++){
            if (v[i] <= v[j]){
                if (poz == -1 || v[poz] > v[j])
                   poz = j;
                if (dm[i] > dm[poz] + 1 || (dm[i] == dm[poz] + 1 && v[poz] < v[next[i]])){
                    dm[i] = dm[poz] + 1;
                    next[i] = poz;
                }
            }
        }
        if (dm[i] == INF)
            dm[i] = 1;
    }
    poz = 1;
    min = v[1];
    for (i=2;i<=n;i++){
      if (v[i] < min){
        min = v[i];
        if (dm[i] < dm[poz] || (dm[i] == dm[poz] && v[i] < v[poz]))
            poz = i;
      }
    }
    printf("%d\n",dm[poz]);
    while (poz != -1){
        printf("%d ",poz);
        poz = next[poz];
    }
    return 0;
}