Pagini recente » Istoria paginii runda/6767557/clasament | Cod sursa (job #1716260) | Clasamentul arhivei Infoarena Monthly | Istoria paginii runda/preoji2014_2/clasament | Cod sursa (job #498781)
Cod sursa(job #498781)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
const int INF = 1 << 30;
void reconst(int aux);
int N;
int V[5002], T[5002], minS[5002];
bool next[5002];
int result = INF, pos;
int main()
{
fin >> N;
for (int i = 1; i <= N; ++i)
fin >> V[i];
int auxm = -INF;
for (int i = N; i >= 1; --i)
if (V[i] > auxm)
{
next[i] = true;
auxm = max(auxm, V[i]);
}
for (int i = 1; i <= N; ++i)
minS[i] = INF;
minS[1] = 1;
for (int i = 2; i <= N; ++i)
{
int maxn = -INF;
for (int j = i - 1; j >= 1; --j)
{
if (maxn < V[j] && V[j] <= V[i] && minS[j] + 1 < minS[i])
{
minS[i] = minS[j] + 1;
T[i] = j;
}
//else if (maxn < V[j] && V[j] <= V[i] && minS[j] + 1 == minS[i] && V[T[i]] > V[j])
// T[i] = j;
if (V[j] <= V[i] && V[j] > maxn)
maxn = V[j];
}
if (minS[i] == INF)
minS[i] = 1;
}
for (int i = 1; i <= N; ++i)
if(next[i] && minS[i] < result)
{
result = minS[i];
pos = i;
}
else if (next[i] && minS[i] == result && V[i] < V[pos])
pos = i;
fout << result << '\n';
reconst(pos);
fin.close();
fout.close();
}
void reconst(int aux)
{
if (aux == 0)
return;
reconst(T[aux]);
fout << aux << ' ';
}