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