Cod sursa(job #2255440)

Utilizator DRLDRLRaul Ronald Galea DRLDRL Data 6 octombrie 2018 23:11:51
Problema Subsir 2 Scor 46
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#pragma once

#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>

using namespace std;

ifstream fin("subsir2.in");
ofstream fout("subsir2.out");

vector<int> sir, dp, pp;



// td(i) - subsirul crescator maximal de lungime minima care incepe cu elementul i = 1 + min(td(j)), j>i, sir[j]<=sir[i], sir[j]<minim pt cond de sir inextensibil

int td(int index) {
	int res, minim = 1<<29;
	if (dp[index] == 1<<29) {
		for (int i = index + 1; i < sir.size(); i++) {
			res = td(i);
			if (sir[i] >= sir[index]) {
				if (res < dp[index]) {
					if (sir[i] < minim) {
						dp[index] = res + 1;
						minim = sir[i];
						pp[index] = i;
					}
				}
			}
		}
		if (dp[index] == 1 << 29) {
			dp[index] = 1;
			pp[index] = index;
		}
	}
	return dp[index];
}

void afis() {
	vector<int> siruriMaximale, siruriMaximaleEgale;
	int sol = 1<<29, lexico = 1<<29, pos;
	for (int i = sir.size() - 1; i >= 0; i--) {
		int ok = 1;
		for (int j = i - 1; j >= 0; j--) {
			if (sir[j] < sir[i]) {
				ok = 0;
				break;
			}
		}
		if (ok == 1) {
			siruriMaximale.push_back(i);
		}
	}
	for (int i = 0; i < siruriMaximale.size(); i++) {
		if (dp[siruriMaximale[i]] < sol) {
			sol = dp[siruriMaximale[i]];
			pos = siruriMaximale[i];
			lexico = sir[siruriMaximale[i]];
		}
		else if (dp[siruriMaximale[i]] == sol) {
			if (sir[siruriMaximale[i]] < lexico) {
				lexico = sir[siruriMaximale[i]];
				pos = siruriMaximale[i];
			}
		}
	}
	fout << sol << "\n";
	while (sol) {
		fout << pos + 1 << " ";
		pos = pp[pos];
		sol--;
	}
}

int main() {
	int n;
	fin >> n;
	sir.resize(n);
	dp.resize(n);
	pp.resize(n);
	fill(dp.begin(), dp.end(), 1 << 29);
	for (int i = 0; i < sir.size(); i++)
		fin >> sir[i];
	td(0);
	afis();
	return 0;
}