Cod sursa(job #927468)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 25 martie 2013 20:20:30
Problema Subsir 2 Scor 4
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <iostream>
#include <fstream>
using namespace std;

int N, sol, start;
int A[1010], dp[1010], sl[1010], pz[1010];

int main()
{
	ifstream fin("subsir2.in");
	fin >> N;
	for (int i = 1; i <= N; i++)
		fin >> A[i];
	
	for (int i = N; i >= 1; i--)
	{
		dp[i] = 1;
		for (int j = i + 1; j <= N; j++)
			dp[i] = max(dp[i], (A[i] <= A[j]) * (dp[j] + 1));
		sol = max(sol, dp[i]);
	}
	
	for (int i = 1; i <= N; i++) sl[i] = 0x3f3f3f3f;
	
	ofstream fout("subsir2.out");
	fout << sol << '\n'; int ds = sol;
	for (int i = sol; i >= 1; i--)
	{
		int prt = 0x3f3f3f3f, poz;
		for (int j = 1; j <= N; j++)
		{
			if (dp[j] == i)
				if (prt > A[j])
				{
					prt = A[j];
					poz = j;
				}
		}
		fout << poz << ' ';
	}

	fout.close();
	return 0;
}