Pagini recente » Cod sursa (job #1351023) | Cod sursa (job #1686178) | Cod sursa (job #1000734) | Cod sursa (job #353872) | Cod sursa (job #1023762)
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 5001
int N, K, Val[MAX], Best[MAX], Prec[MAX], Sol[2][MAX];
bool FirstSolution;
void GetTrace(int N, int K) {
if (K != -1) {
GetTrace(N - 1, Prec[K]);
Sol[1][N] = K;
}
}
bool LexicographicalLower() {
for (int i = 0; i < K; i++) {
if (Val[Sol[1][i]] < Val[Sol[0][i]]) return 1;
if (Val[Sol[1][i]] > Val[Sol[0][i]]) return 0;
}
return 0;
}
int main(){
freopen("subsir2.in","r",stdin);
freopen("subsir2.out","w",stdout);
scanf("%d", &N);
for (int i = 0; i < N; i++) {
scanf("%d", &Val[i]);
}
Best[0] = 1;
for (int i = 0; i < N; i++) {
Best[i] = 1;
Prec[i] = -1;
for (int j = i - 1; j >= 0; j--)
if (Val[j] <= Val[i] && Best[j] + 1 > Best[i]) {
Best[i] = Best[j] + 1;
Prec[i] = j;
} else if (Val[j] <= Val[i] && Best[j] + 1 == Best[i] && (Prec[i] == -1 || Val[j] < Val[Prec[i]])) {
Prec[i] = j;
}
if (Best[i] > K) K = Best[i]; // subsir maxim
}
FirstSolution = 0;
for (int i = 0; i < N; i++)
if (Best[i] == K) {
GetTrace(K - 1, i); // extrag sirul
if (!FirstSolution || LexicographicalLower()) {
for (int j = 0; j < K; j++) Sol[0][j] = Sol[1][j];
FirstSolution = 1;
}
}
// for (int i = 0; i < N; i++) printf("%d ", Best[i]); printf("\n");
printf("%d\n", K);
for (int i = 0; i < K; i++) printf("%d ", Sol[0][i] + 1);
return 0;
}