Cod sursa(job #2631250)

Utilizator CraniXortDumitrescul Eduard CraniXort Data 29 iunie 2020 16:26:02
Problema Subsir 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.84 kb
///Ciudata problema
#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;

void bu() {
	int minim;
	for (int i = sir.size()-1; i >=0; i--) {
		minim = 1 << 29;
		for (int j = i + 1; j < sir.size(); j++) {
			if (sir[j] >= sir[i] && sir[j]<minim) {
				if (dp[j] < dp[i]) {
						dp[i] = dp[j];
						pp[i] = j;
				}
				else if (dp[j] == dp[i]) {
						pp[i] = j;
				}
				minim = sir[j];
			}
		}
		if (dp[i] == 1 << 29) {
			dp[i] = 1;
			pp[i] = i;
		}
		else {
			dp[i]++;
		}
	}
}

void afis() {
	vector<int> siruriMaximale;
	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];
			}
		}
	}
	/*
	int vmic = 1 << 29, lmic = 1 << 29, pos, sol;
	for (int i = 0; i < sir.size(); i++) {
		if (sir[i] < vmic && dp[i] <= lmic) {
			vmic = sir[i];
			lmic = dp[i];
			pos = i;
		}
{1}
	}
	sol = lmic;
	*/
	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];
	bu();
	afis();
	return 0;
}