Pagini recente » Cod sursa (job #252427) | Cod sursa (job #2555015) | Cod sursa (job #3194094) | Cod sursa (job #638813) | Cod sursa (job #1135273)
#include <iostream>
#include <string>
#include <fstream>
using namespace std;
const int Nmax = 5005;
const int INF = 10000000;
int A[Nmax];
int D[Nmax]; // lungimea celui mai scurt subsir maximal
int P[Nmax]; // parinte
int Res[Nmax];
int main()
{
ifstream f ("subsir2.in");
ofstream g ("subsir2.out");
int N;
f >> N;
for (int i = 0; i < N; i++)
{
f >> A[i];
P[i] = -1;
D[i] = 1;
}
int premax;
for (int i = 1; i < N; i++)
{
premax = -INF;
for (int j = i-1; j >-1; j--) {
if (A[j] <= A[i] && A[j] > premax) {
premax = A[j];
if (D[i] == 1 || D[j]+1 < D[i])
{
D[i] = D[j]+1;
P[i] = j;
}
}
}
}
premax = -INF;
int best = INF;
int start = -1;
for (int i = N-1; i >-1; i--) {
if (A[i] > premax) {
premax = A[i];
if (best > D[i])
{
best = D[i];
start = i;
}
}
}
/*
g << premax << '\t' << best << '\t' << start << endl;
for (int i = 0; i < N; i++)
g << D[i] << '_';
g << endl;
for (int i = 0; i < N; i++)
g << P[i] << '_';
g << "\nAnswer:\n";
*/
/*
for (int i = N-1; i >-1; i--)
if (D[i] == best) { start = i; break; }
*/
int cnt = 0;
while (start > -1) {
Res[cnt] = start+1;
start = P[start];
cnt++;
}
g << best << '\n';
for (int i = cnt-1; i>-1; i--)
g << Res[i] << ' ';
g << '\n';
return 0;
}