Pagini recente » Cod sursa (job #2753934) | Cod sursa (job #1103784) | Cod sursa (job #296495) | Monitorul de evaluare | Cod sursa (job #1463653)
#include <fstream>
using namespace std;
ifstream fin ("subsir2.in");
ofstream fout ("subsir2.out");
int N, V[5010], DP[5010], Poz[5010];
int main()
{
fin >> N;
for (int i = 1; i <= N; i++) fin >> V[i];
int maxim = 0, start, minim, minim_nr;
for (int i = N; i >= 1; i--)
{
DP[i] = 1;
Poz[i] = i;
minim = 1000000000;
minim_nr = 1000000000;
for (int j = i + 1; j <= N; j++)
{
if (V[i] <= V[j])
{
if (DP[j] + 1 < minim_nr && V[j] < minim)
{
DP[i] = DP[j] + 1;
Poz[i] = j;
minim_nr = DP[i];
minim = min (minim, V[j]);
}
else if (DP[j] + 1 == minim_nr && V[j] < minim)
{
Poz[i] = j;
minim = V[j];
}
}
}
}
minim = 1000000000;
for (int i = 1; i <= N; i++)
{
if (minim > V[i])
{
minim = V[i];
start = i;
}
}
fout << DP[start] << '\n';
while (Poz[start] != start)
{
fout << start << ' ';
start = Poz[start];
}
fout << start << '\n';
return 0;
}