Pagini recente » Borderou de evaluare (job #523490) | Borderou de evaluare (job #2617482) | Borderou de evaluare (job #1820814) | Borderou de evaluare (job #1480900) | Cod sursa (job #2682127)
#include <fstream>
using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
int main()
{
int a[5001];
int dp[5001], b[5001] = {}, p[5001] = {};
//dp[i] = lungimea minima a unui subsir cresc. maximal ce porneste din pozitia i
//p[i] = parintele lui i in cazul lui dp[i] optim si solutia sa fie minim lexicografica (adica urmatorul element din subsirul optim)
int n, i, j, rasp, m;
fin >> n;
for (i = 1; i<=n; i++)
{
fin >> a[i];
dp[i] = n+1;
}
for (i = n; i>=1; i--)
{
m = 1000001;
for (j = i+1; j<=n; j++)
if (a[i] <= a[j])
{
b[j] = 1;
if (a[j] < m)
{
if (dp[i] >= 1 + dp[j])
{
dp[i] = 1 + dp[j];
p[i] = j;
}
m = a[j];
}
}
if (dp[i] > n)
dp[i] = 1;
}
rasp = 0;
dp[0] = n+1;
for (i = 1; i<=n; i++)
if (b[i] == 0 && (dp[rasp] > dp[i] || (dp[rasp] == dp[i] && a[rasp] > a[i])))
rasp = i;
fout << dp[rasp] << '\n';
for (; rasp != 0; rasp = p[rasp])
fout << rasp << ' ';
return 0;
}