Pagini recente » Cod sursa (job #1858000) | Cod sursa (job #816332) | Clasament Teme ACM Unibuc 2013 | Cod sursa (job #2378367) | Cod sursa (job #1117485)
#include <fstream>
#define in "subsir2.in"
#define out "subsir2.out"
#define Max_Size 5009
#define oo 10000000
std :: ifstream f(in);
std :: ofstream g(out);
int N, minim, A[Max_Size], DP[Max_Size], Tata[Max_Size];
bool Viz[Max_Size];
int main() {
f >> N;
for(int i = 1; i <= N; ++i) f >> A[i];
DP[N] = 1;
for(int i = N - 1; i >= 1; --i) {
minim = DP[i] = oo;
Tata[i] = -1;
for(int j = i + 1; j <= N; ++j) {
if(A[i] <= A[j] && minim > A[j]) {
minim = A[j];
if(DP[i] > DP[j] + 1 || DP[i] == DP[j] + 1 && A[j] < A[ Tata[i] ] )
DP[i] = DP[j] + 1, Tata[i] = j;
}
if(A[i] <= A[j]) Viz[j] = 1;
}
}
int beg; minim = oo;
for(int i = 1; i <= N; ++i)
if(minim > DP[i] && !Viz[i]) minim = DP[i], beg = i;
else
if(minim == DP[i] && !Viz[i] && A[i] < A[beg]) beg = i;
g << minim << '\n';
while(minim) {
g << beg << ' ';
beg = Tata[beg], --minim;
}
g.close();
return 0;
}