Pagini recente » Cod sursa (job #244396) | Cod sursa (job #1637832) | Cod sursa (job #1774379) | Cod sursa (job #1947607) | Cod sursa (job #2947916)
#include <fstream>
#include <bitset>
using namespace std;
const int N = 5000;
const int INF = 1 << 20;
int lung[N], v[N], urm[N], n;
int main()
{
ifstream in("subsir2.in");
ofstream out("subsir2.out");
in >> n;
for (int i = 0; i < n; i++)
{
in >> v[i];
}
bitset <N> prim;
prim.set();
lung[n - 1] = 1;
urm[n - 1] = -1;
for (int i = n - 2; i >= 0; i--)
{
lung[i] = n + 1;
int minim = INF;
for (int j = i + 1; j < n; j++)
{
if (v[i] <= v[j])
{
if (v[j] < minim)///pot pune v[i] la inc. sirului optim din j
{
minim = v[j];
if (lung[j] <= lung[i])
{
lung[i] = lung[j];
urm[i] = j;
}
}
prim[j] = 0;
}
}
if (lung[i] == n + 1)
{
lung[i] = 1;
urm[i] = -1;
}
else
{
lung[i]++;
}
}
int p = 0, lmin = n + 1;
for (int i = 0; i < n; i++)
{
//out << i << ": " << lung[i] << " " << prim[i] << " " << urm[i] << "\n";
if (prim[i] && (lung[i] < lmin || (lung[i] == lmin && v[i] < v[p])))
{
lmin = lung[i];
p = i;
}
}
out << lmin << "\n";
while (p != -1)
{
out << p + 1 << " ";
p = urm[p];
}
in.close();
out.close();
return 0;
}