Pagini recente » Cod sursa (job #1230383) | Cod sursa (job #2754724) | Cod sursa (job #2495094) | Cod sursa (job #883573) | Cod sursa (job #1562585)
#include <fstream>
#define NMAX 5007
#define INF 1 << 25
using namespace std;
ifstream in("subsir2.in");
ofstream out("subsir2.out");
int Dp[NMAX + 1], a[NMAX + 1], Last[NMAX + 1];
int n, Min, Nr;
int main(void){
in >> n;
for (int i = 1; i <= n; ++i)
in >> a[i];
a[0] = -INF;
for (int i = n; i >= 0; --i){
Min = Dp[i] = INF;
for (int j = i + 1; j <= n; ++j){
if ((a[j] < Min) && (a[i] <= a[j])){
Min = a[j];
Nr = Dp[j] + 1;
if ((Dp[i] == Nr) && (a[j] < a[Last[i]]))
Last[i] = j;
if (Nr < Dp[i]){
Dp[i] = Nr;
Last[i] = j;
}
}
}
if (Dp[i] == INF){
Dp[i] = 1;
Last[i] = i;
}
}
out << Dp[0] - 1 << "\n";
int k = 0;
while(k != Last[k]){
out << Last[k] << " ";
k = Last[k];
}
return 0;
}