Mai intai trebuie sa te autentifici.
Cod sursa(job #953809)
| Utilizator | Data | 27 mai 2013 13:13:07 | |
|---|---|---|---|
| Problema | Subsir 2 | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 1.11 kb |
#include <fstream>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
int N;
int A[5002], D[5002], T[5002];
int ST[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;
ST[0] = 0;
for (int j = i + 1; j <= N; ++j)
if (A[i] <= A[j])
{
while (ST[0] != 0 && A[ST[ST[0]]] > A[j])
--ST[0];
ST[++ST[0]] = j;
if (ST[0] == 1 && (D[ST[1]] + 1 < D[i] || (D[ST[1]] + 1 == D[i] && A[ST[1]] < A[T[i]])))
{
D[i] = D[ST[1]] + 1;
T[i] = ST[1];
}
}
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();
}
