Pagini recente » Cod sursa (job #472122) | Cod sursa (job #149357) | Cod sursa (job #1209553) | Cod sursa (job #489732) | Cod sursa (job #953811)
Cod sursa(job #953811)
#include <fstream>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
int N;
int A[5002], D[5002], T[5002];
int result = INF, where;
int main()
{
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
fin >> N;
for (int i = 1; i <= N; ++i)
fin >> A[i];
for (int i = N; i >= 1; --i)
{
D[i] = INF;
int minnow = -1;
for (int j = i + 1; j <= N; ++j)
if (A[i] <= A[j])
{
if (minnow == -1 || A[j] < A[minnow]) minnow = j;
if (minnow != -1 && (D[minnow] + 1 < D[i] || (D[minnow] + 1 == D[i] && A[minnow] < A[T[i]])))
{
D[i] = D[minnow] + 1;
T[i] = minnow;
}
}
if (D[i] == INF) D[i] = 1;
}
int minnow = -INF;
for (int i = 1; i <= N; ++i)
{
if (minnow == -INF || A[minnow] > A[i])
minnow = i;
if (minnow == i && (result > D[i] || (result == D[i] && A[i] < A[where])))
{
result = D[i];
where = i;
}
}
fout << result << '\n';
while (where != 0)
{
fout << where << ' ';
where = T[where];
}
fout << '\n';
fin.close();
fout.close();
}