Pagini recente » Cod sursa (job #2350518) | Cod sursa (job #446891) | Cod sursa (job #1014192) | Cod sursa (job #391504) | Cod sursa (job #531179)
Cod sursa(job #531179)
#include <fstream.h>
#define N 5001
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
long long a[N], n, p[N], L[N], ValMin, best,start,ok;
void scmax(){
int i,j;
best = 5001;
start = n;
for (i=n; i>0; i--){
L[i] = 5001; // lungimea sirului maximal i
p[i] = i; // urmatorul element dupa i
ValMin = 1000001;
ok = 0;
for (j=i+1; j<=n; j++){
if(a[i] <= a[j] && a[j]<ValMin){
ValMin = a[j];
if (L[j]+1 < L[i]){
L[i] = L[j] + 1;
p[i] = j;
ok = 1;
} else if (L[i] == L[j]+1 && a[j] < a[p[i]]){
p[i] = j;
ok = 1;
}
}
}
if (!ok) L[i] = 1;
}
}
int main(){
long i,j;
fin>>n;
for (i=1;i<=n; i++)
fin>>a[i];
scmax();
//fout<<L[start]<<"\n";
best = ValMin = 1000001;
for (i=1;i<=n;i++)
if (ValMin > a[i]){
ValMin = a[i];
if (L[i] == best && a[i] < a[start])
start = i;
if (L[i] < best) {best = L[i]; start= i;}
}
fout<<best<<"\n";
for (i=start,j=1;i<=best;i++,j=p[j])
fout<<j<<" ";
return 0;
}