Pagini recente » Cod sursa (job #1874713) | Cod sursa (job #2878448) | Cod sursa (job #2786950) | Cod sursa (job #2330167) | Cod sursa (job #2631250)
///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;
}