Pagini recente » Cod sursa (job #413925) | Cod sursa (job #2050305) | Cod sursa (job #2455753) | Cod sursa (job #493121) | Cod sursa (job #1463578)
#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;
for (int i = N; i >= 1; i--)
{
DP[i] = 1;
Poz[i] = -1;
int minim = 1000000000;
for (int j = i + 1; j <= N; j++)
{
if (V[i] <= V[j])
{
if (DP[i] < DP[j] + 1)
{
DP[i] = DP[j] + 1;
Poz[i] = j;
minim = min (minim, V[j]);
}
else if (DP[i] == DP[j] + 1 && V[j] < minim)
{
Poz[i] = j;
minim = V[j];
}
}
}
if (DP[i] > maxim) maxim = DP[i], start = i;
else if (DP[i] == maxim && V[i] < V[start]) start = i;
}
int minim = 1000000000;
for (int i = 1; i <= N; i++)
{
if (minim > V[i])
{
minim = V[i];
start = i;
}
}
fout << DP[start] << '\n';
while (start != -1)
{
fout << start << ' ';
start = Poz[start];
}
return 0;
}