Cod sursa(job #960504)

Utilizator primulDarie Sergiu primul Data 10 iunie 2013 16:59:19
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
//TC
 
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cassert>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
 
#define forn(a,b,c) for(int (a)=(b);(a)<=(c);(a)++)
#define forr(a,b,c) for(int (a)=(b);(a)>=(c);(a)--)
#define foreach(a,b) for( typeof( (b).begin() ) a=(b).begin(); (a)!=(b).end() ; (a)++ )
#define foreachr(a,b) for( typeof( (b).rbegin() ) a=(b).rbegin(); (a)!=(b).rend() ; (a)++ )
#define dg(x)  cerr <<#x<<':'<<x<<" "
#define dbg(x)  cerr <<#x<<':'<<x<<endl
#define SET(A,b) memset(A,b,sizeof (A) )
#define SIZE(A) ((int)(A).size())
#define ALL(A) (A).begin(),(A).end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define num(a) (1LL<<(a))
using namespace std;
 
typedef double dbl;
typedef long long Lint;
typedef pair<int,int> ii;
typedef pair<Lint,Lint> Lii;
 
const int MAXN = 5010;
 
int ar[MAXN];
int dn[MAXN];
int go[MAXN];
 
const int inf = 1e8;
 
int main(){
     
    freopen("subsir2.in","r",stdin);
    freopen("subsir2.out","w",stdout);
     
    int n;
     
    scanf("%d",&n);
     
    forn(i,1,n)
        scanf(" %d",ar+i);
     
    ar[n+1]=inf;
    ar[0]=-inf;
     
    int t;
     
    forr(i,n,0)
    {
        //~ dbg(i);
        t=inf+1;
        dn[i]=inf;
        forn(j,i+1,n+1)
        {
            if( ar[j]>=ar[i] && t>ar[j] && ( dn[i]>dn[j]+1 || (dn[i]==dn[j]+1 && ar[go[i]]>ar[j] ) ))
            {
                //~ printf("%d -> %d\n",i,j);
                dn[i]=dn[j]+1,go[i]=j;
            }
            if(ar[j]>=ar[i])
                t=min(t,ar[j]);
        }
        //~ printf("%d %d\n",dn[i],go[i]);
    }
     
    cout << dn[0] -1 << endl;
     
    int x=0;
    while(go[x]!=n+1)
    {
        printf("%d ",go[x]);
        x=go[x];
    }
    puts("");
         
     
    return 0;
     
}