Cod sursa(job #927465)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 25 martie 2013 20:18:14
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 = 1; i <= N; i++)
	{
		if (dp[i] >= sol)
			if (sl[dp[i]] > A[i])
			{
				sl[dp[i]] = A[i];
				pz[dp[i]] = i;
				sol = dp[i] - 1;
			}
	}
	for (int i = ds; i >= 1; i--)
		fout << pz[i] << ' ';
	
	fout.close();
	return 0;
}