Pagini recente » Cod sursa (job #3203219) | Cod sursa (job #2638158) | Cod sursa (job #178912) | Cod sursa (job #2337924) | Cod sursa (job #2560537)
#include <fstream>
using namespace std;
ifstream f("subsir2.in");
ofstream g("subsir2.out");
int n, i, j;
int v[5001];
int best[5001], maxim;
bool ok[5001];
int lg, lg1, poz;
int rez[5001];
int main()
{
f >> n;
for (i=1; i<=n; i++)
{
f >> v[i];
maxim = 0;
for (j=1; j<i; j++)
if (v[j] <= v[i])
maxim = max(maxim, best[j]);
for (j=1; j<i; j++)
if (best[j] == maxim)
ok[j] = 1;
best[i] = maxim + 1;
}
lg = n, poz = 0;
for (i=1; i<=n; i++)
if (!ok[i] && best[i] < lg)
lg = best[i], poz = i;
else if (!ok[i] && best[i] == lg && v[i] < v[poz])
poz = i;
lg1 = lg;
while (lg)
{
rez[lg] = poz;
lg--;
for (i=poz-1; i; i--)
if (best[i] == lg && v[i] < v[poz])
poz = i;
}
g << lg1 << "\n";
for (i=1; i<=lg1; i++)
g << rez[i] << " ";
return 0;
}