Pagini recente » Cod sursa (job #448458) | Cod sursa (job #1851155) | Cod sursa (job #3348859) | Cod sursa (job #3299097) | Cod sursa (job #973052)
Cod sursa(job #973052)
#include<stdio.h>
#include<vector>
#include<algorithm>
#define NMAX 5007
using namespace std;
vector < int > SOL;
int best[NMAX], a[NMAX], n, MAX, poz, last_poz;
inline int max(int a, int b)
{
if(a > b)
return a;
return b;
}
int main(){
freopen("subsir2.in", "r", stdin);
freopen("subsir2.out", "w", stdout);
scanf("%d", &n);
for(int i = 1; i <= n; ++ i)
scanf("%d", &a[i]);
best[1] = 1;
for(int i = 2; i <= n; ++ i){
for(int j = 1; j < i; ++ j)
if(a[i] >= a[j])
best[i] = max(best[i], best[j] + 1);
MAX = max(MAX, best[i]);
}
int Number = 20000000;
for(int i = 1; i <= n; ++ i)
if(best[i] == MAX)
if(Number >= a[i]){
Number = a[i];
poz = i;
}
printf("%d\n", MAX);
SOL.push_back(poz);
-- MAX;
while(MAX > 0)
{
last_poz = poz;
int Number2 = 2000000000, poz = 0;
for(int i = last_poz; i >= 1; -- i)
if(best[i] == MAX && a[i] <= Number)
if(Number2 >= a[i]){
Number2 = a[i];
poz = i;
}
SOL.push_back(poz);
Number = Number2;
-- MAX;
}
reverse(SOL.begin(), SOL.end());
for(int i = 0; i < SOL.size(); ++ i)
printf("%d ", SOL[i]);
return 0;
}