Cod sursa(job #2682127)

Utilizator popoviciAna16Popovici Ana popoviciAna16 Data 7 decembrie 2020 20:50:40
Problema Subsir 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#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;
}