Pagini recente » Cod sursa (job #332735) | Cod sursa (job #841321) | Cod sursa (job #809019) | Cod sursa (job #2953504) | Cod sursa (job #1481512)
#include <bits/stdc++.h>
#define oo 2000000
using namespace std;
int a[5005], best[5005], n;
void Citire()
{
int i;
ifstream fin("subsir2.in");
fin >> n;
for (i = 1; i <= n; i++)
fin >> a[i];
fin.close();
}
void Rezolva()
{
int i, maxx, lgmin, j, p, x, minim;
best[n] = 1;
for (i = n - 1; i >= 1; --i)
{
x = a[i];
/// maxx retine cea mai mica valoare strict mai mare ca x
maxx = oo;
lgmin = oo;
for (j = i + 1; j <= n; ++j)
if (x <= a[j] && a[j] < maxx && lgmin >= best[j])
{
maxx = a[j];
lgmin = best[j];
}
if (lgmin == oo) best[i] = 1;
else best[i] = 1 + lgmin;
}
/// caut cea mai mica valoare best[i], cu a[i]=min{a1,a2,...ai}.
x = a[1]; p = 1;
for (i = 2; i <= n; ++i)
if (best[i] <= best[p] && a[i] < x)
{
p = i;
x = a[i];
}
ofstream fout("subsir2.out");
fout << best[p] << "\n";
x = a[p];
fout << p << " ";
for (int pas = best[p]-1; pas >= 1; pas--)
{
/// caut o pozitie in p..n cu best[i]=pas si x<=a[i], a[i]-minim
minim = oo; j = -1;
for (i = p + 1; i <= n; i++)
if (best[i] == pas && x <= a[i] && minim > a[i])
{
j = i;
minim = a[i];
}
p = j;
fout << p << " ";
}
fout << "\n";
fout.close();
}
int main()
{
Citire();
Rezolva();
return 0;
}