Pagini recente » Cod sursa (job #2622846) | Cod sursa (job #2040278) | Cod sursa (job #1307398) | Cod sursa (job #1133720) | Cod sursa (job #1142155)
#include <iostream>
#include <fstream>
using namespace std;
const int Nmax = 5005;
const int INF = 10000000;
int A[Nmax];
int D[Nmax];
int Next[Nmax];
int N;
int main()
{
ifstream f ("subsir2.in");
ofstream g ("subsir2.out");
f >> N;
for (int i = 0; i < N; i++) {
f >> A[i];
D[i] = 1;
Next[i] = -1;
}
int premin = INF;
for (int n = N-1; n >-1; n--) {
premin = INF;
for (int i = n+1; i < N; i++) {
if (A[i] >= A[n] && A[i] < premin) {
premin = A[i];
if (D[n] == 1 || D[n] >= D[i] + 1) {
D[n] = D[i] + 1;
if (A[Next[n]] > A[i] || Next[n] == -1)
Next[n] = i;
}
}
}
}
int best = INF;
int start = -1;
premin = INF;
for (int i = 0; i < N; i++) {
if (A[i] < premin) {
premin = A[i];
if (D[i] <= best) {
best = D[i];
if (start == -1 || A[i] < A[start])
start = i;
}
}
}
/*
for (int i = 0; i < N; i++)
g << D[i] << (i==N-1?'\n':'_');
for (int i = 0; i < N; i++)
g << Next[i] << (i==N-1?'\n':'_');
*/
g << best << '\n';
while (start > -1) {
g << start + 1 << ' ';
start = Next[start];
}
g << '\n';
return 0;
}